当前位置: 首页 > 工具软件 > Quick[select] > 使用案例 >

[Algorithm]Quick Select问题

仲孙向明
2023-12-01

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();
    }  
}





 类似资料: