LeetCode #274 H-Index：我的Python解法时间复杂度是多少？

问题回顾 #

给定整数数组citations，其中每个元素代表一篇论文的被引用次数，返回研究者的h-index——即满足「至少h篇论文被引用至少h次」的最大h值。

你的解法逻辑 #

你维护了一个名为space的列表，遍历每篇论文的引用数：

• 若space为空，且当前引用数大于0，则将其加入列表；
• 若space不为空，且当前引用数大于space的长度，则将其加入列表；随后检查列表中的最小值是否小于当前space的长度（也就是当前候选的h值），若是则移除该最小值；
• 最终返回space的长度作为h-index。

时间复杂度拆解 #

我们从每一步操作的时间消耗入手分析：

1. 外层循环：遍历整个citations数组，共执行n次（n为数组长度），这部分是O(n)。
2. 循环内的核心操作：
   • min(space)：需要遍历整个space列表找到最小值，时间复杂度为O(k)，其中k是当前space的长度（k最大为n）；
   • space.remove(min(space))：移除元素时需要先定位到最小值的位置，再移动后续元素填补空位，时间复杂度同样为O(k)。

最坏情况时间复杂度 #

当所有论文的引用数都远大于n时（比如输入为[100, 100, ..., 100]共n个元素），每次循环都会执行append，随后触发min(space)和remove操作。此时k从1逐步增长到n，总时间消耗为：
$$O(1 + 2 + 3 + ... + n) = O(\frac{n(n+1)}{2}) = O(n^2)$$

结论 #

你的解法的最坏时间复杂度为O(n²)，平均情况下的时间复杂度也为O(n²)，因为多数场景下都会频繁触发min和remove这两个线性时间操作。

内容的提问来源于stack exchange，提问作者helpMePlz