題目鏈接
tag:
- Medium谅阿；
- Binary Search;
question
??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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note: You may assume k is always valid, 1 ≤ k ≤ array's length.
解法一：
??求數(shù)組中第k大的數(shù)字，當(dāng)然首先想到的應(yīng)該是給數(shù)組排序酬滤。利用c++的STL中的 sort() 排序方法签餐，兩行代碼就搞定了，代碼如下：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
解法二：
??利用 priority_queue 的自動排序的特性盯串，跟上面的思路上沒有什么區(qū)別氯檐，代碼如下：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> q(nums.begin(), nums.end());
for (int i=0; i<k-1; ++i) {
q.pop();
}
return q.top();
}
};
解法三：
??上面兩種方法雖然簡潔，但是不是本題真正想考察的東西体捏。這道題最好的解法應(yīng)該是用快速排序 Quick Sort 的思想冠摄，這里排序的方向是從大往小排〖哥裕快排核心思想是每次都要先找一個中樞點(diǎn)Pivot河泳，然后遍歷其他所有的數(shù)字，像這道題從大往小排的話年栓，就把大于中樞點(diǎn)的數(shù)字放到左半邊拆挥，把小于中樞點(diǎn)的放在右半邊，這樣中樞點(diǎn)是整個數(shù)組中第幾大的數(shù)字就確定了某抓，雖然左右兩部分各自不一定是完全有序的纸兔，但是并不影響本題要求的結(jié)果，因?yàn)樽蟀氩糠值乃兄刀即笥谟野氩糠值娜我庵捣窀保晕覀兦蟪鲋袠悬c(diǎn)的位置汉矿，如果正好是k-1，那么直接返回該位置上的數(shù)字备禀；如果大于k-1洲拇，說明要求的數(shù)字在左半部分，更新右邊界曲尸，再求新的中樞點(diǎn)位置呻待；反之則更新右半部分，求中樞點(diǎn)的位置队腐；不得不說蚕捉，這個思路真的是巧妙啊，代碼如下：
class Solution {
public:
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];
else if (pos > k - 1) right = pos - 1;
else left = pos + 1;
}
}
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[left], l = left + 1, r = right;
while (l <= r) {
if (nums[l] < pivot && nums[r] > pivot) {
swap(nums[l++], nums[r--]);
}
if (nums[l] >= pivot) ++l;
if (nums[r] <= pivot) --r;
}
swap(nums[left], nums[r]);
return r;
}
};
