我的问题来自下面的leetcode解决方案，我无法理解为什么会这样 O(k+(n-k)log(k))。
补充：也许复杂性不是那样，实际上我不知道时间的复杂性 heappush() 和 heappop()
# O(k+(n-k)lgk) time, min-heap
def findKthLargest(self, nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
for _ in xrange(len(nums)-k):
heapq.heappop(heap)
return heapq.heappop(heap)
heapq 是一个二进制堆，有O（log n） push 和O（log n） pop。见 heapq源代码。
您显示的算法需要O（n log n）将所有项目推送到堆上，然后使用O（（n-k）log n）来查找第k个最大元素。因此复杂性将是O（n log n）。它还需要O（n）额外空间。
您可以在O（n log k）中执行此操作，使用O（k）额外空间稍微修改算法。我不是Python程序员，所以你必须翻译伪代码：
create a new min-heap
push the first k nums onto the heap
for the rest of the nums:
if num > heap.peek()
heap.pop()
heap.push(num)
// at this point, the k largest items are on the heap.
// The kth largest is the root:
return heap.pop()
这里的关键是堆只包含到目前为止看到的最大项目。如果一个项目小于目前为止看到的第k个最大项目，那么它永远不会被放到堆上。最坏的情况是O（n log k）。
其实， heapq 有一个 heapreplace 方法，所以你可以替换这个：
if num > heap.peek()
heap.pop()
heap.push(num)
同
if num > heap.peek()
heap.replace(num)
另外，推动第一个的替代方案 k items是创建第一个列表 k 物品和电话 heapify。更优化（但仍然是O（n log k））算法是：
create array of first `k` items
heap = heapify(array)
for remaining nums
if (num > heap.peek())
heap.replace(num)
return heap.pop()
你也可以打电话 heapify 在整个阵列上，然后弹出第一个 n-k 项目，然后采取顶部：
heapify(nums)
for i = 0 to n-k
heapq.heappop(nums)
return heapq.heappop(nums)
那更简单。不确定它是否比我之前的建议更快，但它修改了原始数组。复杂性是O（n）构建堆，然后O（（n-k）log n）为pops。所以它是O（（n-k）log n）。最坏情况O（n log n）。