Leetcode215:数组中的第K个最大元素[CPP][GO]

问题描述

在未排序的数组中找到第 k 个最大的元素。请注意&＃xff0c;你需要找的是数组排序后的第 k 个最大的元素&＃xff0c;而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k &＃61; 2
输出: 5


示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k &＃61; 4
输出: 4


说明:

你可以假设 k 总是有效的&＃xff0c;且 1 ≤ k ≤ 数组的长度。

思路

1. 排序的思想&＃xff0c;很简单&＃xff0c;直接排好顺序&＃xff0c;然后直接取就好了。因为快排一趟可以确定&＃xff0c;按从小到大的顺序的话&＃xff0c;到n-k的位置就能确定是第k大的元素&＃xff0c;可以减少一些多余操作&＃xff0c;时间复杂度是O(nlog2n)O(nlog_{2}{n})O(nlog2​n)&＃xff0c;空间复杂度是$O(1)$
2. 使用最小堆&＃xff0c;维持一个最小堆&＃xff0c;然后遍历数组&＃xff0c;当数组中的数大于堆顶元素&＃xff0c;让堆顶出去&＃xff0c;然后调整堆结构。时间复杂度是O(nlog2k)O(nlog_2k)O(nlog2​k),空间复杂度是$O(k)$

GO

go只写了小顶堆

func adjustHeap(heap []int,i,k int){child :&＃61; i*2&＃43;1for child < k{if child &＃43; 1 < k && heap[child] > heap[child&＃43;1]{child&＃43;&＃43;}if heap[child] > heap[i]{break}heap[child],heap[i] &＃61; heap[i],heap[child]i &＃61; childchild &＃61; i * 2 &＃43; 1}
}func findKthLargest(nums []int, k int) int {minHeap :&＃61; make([]int,k)copy(minHeap,nums)for i :&＃61; k/2-1;i>&＃61;0;i--{adjustHeap(minHeap,i,k)}for i :&＃61; k;i < len(nums);i&＃43;&＃43;{if nums[i] > minHeap[0]{minHeap[0] &＃61; nums[i]adjustHeap(minHeap,0,k)}}return minHeap[0]
}


Cpp

库函数&＃xff08;快排&＃xff09;

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int n &＃61; nums.size();sort(nums.begin(),nums.end(),[](int &a,int &b){return a > b;});return nums[k-1];}
};


快排

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int sz &＃61; nums.size();if(nums.empty() || k > sz)return -1;int n &＃61; sz - k;int right &＃61; sz - 1,left &＃61; 0;while(left < right){int idx &＃61; partition(nums,left,right);if(idx &＃61;&＃61; n)return nums[n];if(idx > n)right &＃61; idx - 1;else left &＃61; idx&＃43;1;}return nums[n];}int partition(vector<int> &nums,int left,int right){int tmp &＃61; nums[left];while(left < right){while(left < right && nums[right] >&＃61; tmp)right--;nums[left] &＃61; nums[right];while(left < right && nums[left] <&＃61; tmp)left&＃43;&＃43;;nums[right] &＃61; nums[left];}nums[left] &＃61; tmp;return left;}
};


小顶堆

class Solution {void adjustHeap(vector<int> &heap,int i,int k){int child &＃61; i * 2 &＃43; 1;while(child < k){if(child&＃43;1 < k && heap[child] > heap[child&＃43;1])child&＃43;&＃43;;if(heap[child] > heap[i])break; swap(heap[child],heap[i]);i &＃61; child;child &＃61; i * 2 &＃43; 1;}} public:int findKthLargest(vector<int>& nums, int k) {vector<int> minHeap;minHeap.assign(nums.begin(),nums.begin()&＃43;k);//构造小顶堆&＃xff0c;位置k/2-1开始for(int i &＃61; (k/2)-1;i >&＃61; 0;i--)adjustHeap(minHeap,i,k);//从第k个开始&＃xff0c;防止重复for(auto iter &＃61; nums.begin() &＃43; k;iter < nums.end();iter&＃43;&＃43;){if(*iter > minHeap[0]){minHeap[0] &＃61; *iter;adjustHeap(minHeap,0,k);}} return minHeap[0];}
};