一：解题思路
这道题的最简单的做法是，将数组从大到小进行排序，然后取出第k-1的那个元素。Time:O(n*log(n)),Space:O(1)
我们来写下面2种做法。
方法一：我们来维护一个top k的最小堆，遍历一次数组，将数组中的元素加入数组中，最后堆定元素就是第K大的元素。Time:O(n*log(k))优于快速排序,Space:O(k)
方法二：和快速排序法有点类似，需要一个划分partition函数，先选取一个基准(这个基准的选取比较重要，关系到算法的时间复杂度)，然后将大于这个基准的元素放到数组的左边，将小于基准的元素 放到数组的右边。(顺序也可以变，也可以将小于基准的元素放到左边，大于基准的元素放到右边。)，这个算法的最好和平均时间复杂度为:O(n),最坏(即数组一开始就是从小到大的排列的时候)时间复杂度为:O(n^2),空间复杂度为O(1).我们可以采用一种随机算法，将数组中的数据随机打乱这样也可以将算法的时间复杂度变为O(n)。这种算法在实际的运用中有效的原因是，因为实际的数据大多都是随机排列的，所以算法的时间复杂度为：Time:O(n),Space:O(1)
二：完整代码示例 (C++版和Java版)，
方法一C++:
class Solution { private: priority_queue<int, vector<int>, greater<int>> minHeap; public: int findKthLargest(vector<int>& nums, int k) { for (int num : nums) { if (minHeap.size() < k) { minHeap.push(num); } else if (num > minHeap.top()) { minHeap.pop(); minHeap.push(num); } } return minHeap.top(); } };
方法一Java:
class Solution { private Queue<Integer> minHeap=new PriorityQueue<>(); public int findKthLargest(int[] nums, int k) { for(int num:nums) { if(minHeap.size()<k) { minHeap.add(num); } else if(num>minHeap.peek()) { minHeap.poll(); minHeap.add(num); } } return minHeap.peek(); } }
方法二C++:
class Solution { private: int partition(vector<int>& nums, int low, int high) { int pivot = nums[low], i = low, j = high; while (i < j) { while (i < j && nums[j] < pivot) j--; if (i < j) swap(nums[i],nums[j]); while (i < j && nums[i] >= pivot) i++; if (i < j) swap(nums[i],nums[j]); } return i; } public: int findKthLargest(vector<int>& nums, int k) { int low = 0, high = nums.size() - 1; while (low <= high) { int p = partition(nums,low,high); if (p == k - 1) return nums[p]; else if (p > k - 1) high = p - 1; else low = p + 1; } return -1; } };
方法二Java:
class Solution { private void swap(int[] nums,int i,int j) { int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } private int partion(int[] nums,int low,int high) { int pivot=nums[low],i=low,j=high; while(i<j) { while(i<j && nums[j]<pivot) j--; if(i<j) swap(nums,i,j); while(i<j && nums[i]>=pivot) i++; if(i<j) swap(nums,i,j); } return i; } public int findKthLargest(int[] nums, int k) { int low=0,high=nums.length-1; while(low<=high) { int p=partion(nums,low,high); if(p==k-1) return nums[p]; else if(p>k-1) high=p-1; else low=p+1; } return -1; } }
原文：https://www.cnblogs.com/repinkply/p/12662623.html