[Algorithm]Quick Select问题
仲孙向明
5.Kth Largest Element：点击打开链接
例如：[9,3,2,4,8]，k=3，Output:4，也就是第3rd大的是4，[2,3,4,8,9]
思路：1. 用当前数组中间的数作为pivot标杆，用O(n)的时间使得大于pivot的数都在左边部分，小于pivot的数都在右边部分
2. 然后就要进行一轮判断，如果判断出k会在左边部分，右边部分就不用再递归了，同理，如果k会在右边也一样处理。
3. 最后跳出while循环有两种情况，但要分成三种情况判断
如果i<j是最后一次循环，i++使得i向前走一步，j--使得j向前走一步，结果i>j跳出循环，此时的相对位置[...j,i...]
如果i=j是最后一次循环，i++使得i向前走一步，j--使得j向前走一步，结果i>j跳出循环，此时的相对位置[...j,pivot,i...]
注意：1. 思路就是T(n)=O(n)+T(n/2)，所以时间复杂度还是O(n)
但如果用先排序再输出最大值的方法，时间复杂度最好也是O(nlogn)(快排，归并排序)，这就是这题为啥要这么折腾一大圈的原因
2. 和follow up是一样的，两种解法都可以直接用在其上，606.Kth Largest Element II: 点击打开链接
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) {
if(nums==null || nums.length==0 || k<=0){
return -1;
}
return quickSelect(nums,0,nums.length-1,k);
}
private int quickSelect(int[] nums,int start,int end,int k){
if(nums[start]==nums[end]){ //例如数组只有一个数[1],k=1
return nums[start];
}
int i=start;
int j=end;
int pivot=nums[(i+j)/2];
while(i<=j){ //i<=j都会一直循环，所以可知最后跳出循环一定是i>j
while(i<=j && nums[i]>pivot){
i++;
}
while(i<=j && nums[j]<pivot){
j--;
}
if(i<=j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
i++;
j--;
}
}
if(start+k-1<=j){ //判断出k会在左边部分，继续递归左边部分直到找到所求
return quickSelect(nums,start,j,k);
}
if(start+k-1>=i){ //判断出k会在右边部分，继续递归右边部分直到找到所求
return quickSelect(nums,i,end,k-(j-start+1));
}
return nums[j+1]; //i=j是最后一次循环，i++，j--，使得数组分为三部分
} //左边部分小于pivot，右边部分大于pivot，中间有个pivot
} //其实这时候nums[j+1]=pivot，所以返回pivot也可以或者优先队列小顶堆方法，时间复杂度也是O(n)，符合题意
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) { //方法二：小顶堆
Queue<Integer> pQueue=new PriorityQueue<>();
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
}461. Kth Smallest Numbers in Unsorted Array：点击打开链接
class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) { //方法一：quick Select
if(nums==null || nums.length==0 || k<=0){
return -1;
}
return quickSelect(nums,0,nums.length-1,k);
}
private int quickSelect(int[] nums,int start,int end,int k){
if(nums[start]==nums[end]){
return nums[start];
}
int i=start;
int j=end;
int pivot=nums[(i+j)/2];
while(i<=j){
while(i<=j && nums[i]<pivot){
i++;
}
while(i<=j && nums[j]>pivot){
j--;
}
if(i<=j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
i++;
j--;
}
}
if(start+k-1<=j){
return quickSelect(nums,start,j,k);
}
if(start+k-1>=i){
return quickSelect(nums,i,end,k-(j-start+1));
}
return pivot;
}
}class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) { //方法二：大顶堆
if(nums==null || nums.length==0 || k<=0){
return -1;
}
Queue<Integer> pQueue=new PriorityQueue<>(k,Collections.reverseOrder()); //大顶堆的写法一
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
}class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) {
if(nums==null || nums.length==0 || k<=0){
return -1;
}
Queue<Integer> pQueue=new PriorityQueue<>(k,myComparator); //大顶堆的写法二
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
private Comparator<Integer> myComparator=new Comparator<Integer>(){ //自定义比较器
public int compare(Integer a,Integer b){ //a是前一个数，b是后一个数
return b-a; //后一个数-前一个数就是从大到小
}
}; //分号不能少
}class Solution {
/*
* @param k an integer
* @param nums an integer array
* @return kth smallest element
*/
public int kthSmallest(int k, int[] nums) { //大顶堆写法三
if(nums==null || nums.length==0 || k<=0){
return -1;
}
Queue<Integer> pQueue=new PriorityQueue<>(k,new Comparator<Integer>(){ //或者直接写自定义比较器
public int compare(Integer a, Integer b) {
return b-a;
}
});
for(int num:nums){
pQueue.offer(num);
if(pQueue.size()>k){
pQueue.poll();
}
}
return pQueue.peek();
}
}
类似资料：