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.
Credits: Special thanks to @mithmatt for adding this problem and creating all test cases.
Subscribe to see which companies asked this question.
这题我直接想到的就是快速排序，快速排序已经是用了分治算法来实现较快的排序了，
以下是快速排序
void Qsort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = high; int key = a[first]; while(first < last) { while(first < last && a[last] >= key) { --last; } a[first] = a[last]; while(first < last && a[first] <= key) { ++first; } a[last] = a[first]; } a[first] = key; Qsort(a, low, first-1); Qsort(a, first+1, high); }
但是在看了网站给出的答案后，发现了有更快的算法
class Solution { public: int partition(vector<int>& nums, int left, int right) { int pivot = nums[left]; int l = left + 1, r = right; while (l <= r) { if (nums[l] < pivot && nums[r] > pivot) swap(nums[l++], nums[r--]); else if (nums[l] >= pivot) l++; else if (nums[r] <= pivot) r--; } swap(nums[left], nums[r]); return r; } int findKthLargest(vector<int>& nums, int k) { int left = 0, right = nums.size() - 1; while (true) { int pos = partition(nums, left, right); if (pos == k - 1) return nums[pos]; if (pos < k - 1) left = pos + 1; else right = pos - 1; } } };
Initialize left to be 0 and right to be nums.size() - 1;Partition the array, if the pivot is at the k-1-th position, return it (we are done);If the pivot is right to the k-1-th position, update right to be the left neighbor of the pivot;Else update left to be the right neighbor of the pivot.Repeat 2. 但是对其想法的由来却不是很理解。。。希望有大神解答