我有一些不同的代码实现，用于在未排序的数组中查找第K个最大元素。我使用的三个实现都使用最小/最大堆，但我很难计算其中一个的运行时复杂性。
实施1:
int findKthLargest(vector<int> vec, int k)
{
// build min-heap
make_heap(vec.begin(), vec.end(), greater<int>());
for (int i = 0; i < k - 1; i++) {
vec.pop_back();
}
return vec.back();
}
实施2:
int findKthLargest(vector<int> vec, int k)
{
// build max-heap
make_heap(vec.begin(), vec.end());
for (int i = 0; i < k - 1; i++) {
// move max. elem to back (from front)
pop_heap(vec.begin(), vec.end());
vec.pop_back();
}
return vec.front();
}
实施3：
int findKthLargest(vector<int> vec, int k)
{
// max-heap prio. q
priority_queue<int> pq(vec.begin(), vec.end());
for (int i = 0; i < k - 1; i++) {
pq.pop();
}
return pq.top();
}
从我的阅读中，我假设第二个的运行时间是O(n(+O(klogn(=O(n+klogin(。这是因为构建最大堆是在O(n(中完成的，如果我们这样做'k'次，则弹出它将花费O(logn(*k。
然而，这是我感到困惑的地方。对于第一个，使用最小堆，我假设构建堆是O(n(。由于它是一个最小堆，较大的元素在后面。然后，弹出后面的元素'k'次将花费k*O(1(=O(k(。因此，复杂度为O(n+k(。
类似地，对于第三个，我假设复杂性也是O(n+klogn(，与我对最大堆的推理相同。
但是，一些消息来源仍然说，这个问题不能比使用堆/pqs的O(n+klogn(更快地解决！在我的第一个例子中，我认为这个复杂度是O(n+k(。如果我错了，请纠正我。需要帮助thx。
如果实现得当，从最小堆中获得第k个最大元素是O((n-k(*log(n((。从最大堆中获得第k个最大元素是O(k*log(n((。
您的第一个实现根本不正确。例如，如果您想从堆中获得最大的元素(k==1(，则永远不会执行循环体。您的代码假设向量中的最后一个元素是堆上最大的元素。这是不正确的。例如，考虑堆：
1
3 2
这是一个完全有效的堆，它将由向量[1,3,2]表示。您的第一个实现无法从该堆中获得第一个或第二个最大的元素。
第二种解决方案看起来是可行的。
您的前两个解决方案最终会从vec中删除项目。这就是你的意图吗？
第三种解决方案是正确的。构建堆需要O(n(，移除(k-1(个最大的项需要O(((k-1(logn(。然后O(1(访问剩余的最大项目。
还有另一种方法，在实践中可能更快。想法是：
build a min-heap of size k from the first k elements in vec
for each following element
if the element is larger than the smallest element on the heap
remove the smallest element from the heap
add the new element to the heap
return element at the top of the heap
这是O(k(来构建初始堆。那么在最坏的情况下，剩余项为O((n-k(log k(。最坏的情况发生在初始向量按升序排列时。这种情况并不经常发生。在实践中，一小部分项目被添加到堆中，因此您不必执行所有的删除和插入操作。
一些堆实现有一个heap_replace方法，它结合了移除顶部元素和添加新元素这两个步骤。这将复杂性降低一个常数。(即，不是删除O(log k(然后插入O(log k(，而是对顶部元素进行恒定时间的替换，然后用O(logk(将其向下筛选到堆中(。
这是java的堆解决方案。我们从最小堆中移除所有小于第k个元素的元素。之后，我们将在最小堆的顶部有第k个最大的元素。
class Solution {
int kLargest(int[] arr, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b)-> Integer.compare(a, b));
for(int a : arr) {
heap.add(a);
if(heap.size()>k) {
// remove smallest element in the heap
heap.poll();
}
}
// return kth largest element
return heap.poll();
}
}
最坏情况下的时间复杂度将是O(NlogK(，其中N是元素的总数。在堆中插入初始k个元素时，您将使用1个heapify操作。之后，您将使用2个操作(1个插入和1个移除(。因此，这使得最坏情况下的时间复杂度为O(NlogK(。您可以使用其他一些方法对其进行改进，并将堆更新的平均事例时间复杂性提高到Θ(1(。阅读本文了解更多信息。
快速选择：Θ(N(
如果您正在寻找一个平均速度更快的解决方案。基于快速排序的快速选择算法是一个很好的选择。它提供了O(N(和O(1(空间复杂度的平均情况时间复杂度。当然，最坏情况下的时间复杂度是O(N^2(，但随机化枢轴(在下面的代码中使用(在这种情况下产生的概率非常低。以下是用于查找第k个最大元素的快速选择算法的代码。
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickselect(nums, k);
}
private int quickselect(int[] nums, int k) {
int n = nums.length;
int start = 0, end = n-1;
while(start<end) {
int ind = partition(nums, start, end);
if(ind == n-k) {
return nums[ind];
} else if(ind < n-k) {
start = ind+1;
} else {
end = ind-1;
}
}
return nums[start];
}
private int partition(int[] nums, int start, int end) {
int pivot = start + (int)(Math.random()*(end-start));
swap(nums, pivot, end);
int left=start;
for(int curr=start; curr<end; curr++) {
if(nums[curr]<nums[end]) {
swap(nums, left, curr);
left++;
}
}
swap(nums, left, end);
return left;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}