Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given[3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.

Solution

将数组排序，然后直接通过索引返回第k大的数字

int findKthLargest(vector<int>& nums, int k){ sort(nums.begin(), nums.end()); reverse(nums.begin(), nums.end()); return nums[k-1]; }

利用分治思想写出快速选择算法耶鲁大学：QuickSelect算法

#include <iostream> #include <vector> using namespace std; int findKthLargest(vector<int>& nums, int k){ vector<int> left; vector<int> right; int pivot = nums[0]; for(int i = 1; i < nums.size(); i++){ if(nums[i] <= pivot) left.push_back(nums[i]); else right.push_back((nums[i])); } if(k <= right.size()) return findKthLargest(right, k); else if(k-1 == right.size()) return pivot; else return findKthLargest(left, k-right.size()-1); } int main(){ int ary[10] = {3, 2, 1, 5, 6, 4}; vector<int> vec(ary, ary+6); cout<<findKthLargest(vec, 2); }

快速选择算法在LeetCode平台上会出现内存超限（Memory Limit Exceeded）的问题，这与C++中内存的管理模式有关：vector内存空间只会增长，不会减小。