原題：
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.
解題：
看到題目第一反應(yīng)是采用堆排序，但是題目中只要求返回第k大的數(shù)殖侵，比K大的數(shù)的順序不用管，因此悴务，想到采用快速選擇的方式。
快速選擇與快速排序思想相同疆栏，重點(diǎn)是分治殊霞。
思路：
1、遍歷：選取target侧甫，將比target大的元素放置在其右邊，比target小的元素放置到其左邊蹋宦。
2披粟、target的位置 === k 返回
3、target> k 說(shuō)明 說(shuō)明第k大數(shù)在target的左邊
4冷冗、target< k 說(shuō)明第k大數(shù)在target右邊
代碼：
class Solution {
public int findKthLargest(int[] nums, int k) {
return findKthLargest2(nums, k ,0, nums.length - 1);
}
public int findKthLargest2(int[] nums, int k, int start ,int end) {
int flag = nums[start];
int left = start;
int right = end;
while(left < right){
while(left < right && nums[right] <= flag){
right --;
}
nums[left] = nums[right];
while (left < right && nums[left] >= flag){
left ++;
}
nums[right] = nums[left];
}
nums[right] = flag;
if(left == k ){
return nums[left];
}
else if(left > k){
return findKthLargest2(nums, k, start, left - 1);
}
else {
return findKthLargest2(nums, k - left - 1, left + 1, end);
}
}
}
注意：
臨界點(diǎn)的選擇守屉。
總結(jié)：
雖然快速選擇的關(guān)鍵思想是分治，但是蒿辙，在解答過(guò)程中拇泛，干擾我比較長(zhǎng)時(shí)間的是左右兩個(gè)指針挖坑、填坑的過(guò)程思灌。
快速排序的挖坑俺叭、填坑的過(guò)程如下：
定義兩個(gè)指針指向數(shù)組的前后兩端，并選取target泰偿，將target所在位置定義為第一個(gè)坑位熄守；如果從右邊開始的數(shù)據(jù)元素小于target，該元素進(jìn)入坑位，從而形成新的坑位裕照；接著從左邊開始遍歷攒发，如果左側(cè)元素大于target，那么該元素進(jìn)入上一次形成的坑位晋南，進(jìn)而產(chǎn)生更新的坑位晨继，以此規(guī)律遍歷，直到左右兩指針相遇搬俊。最后，target元素進(jìn)入最后產(chǎn)生的坑位中蜒茄；以此結(jié)束了選擇唉擂，保證了target左邊的元素都是比target小的 ，而右邊元素都是比target大的檀葛。
