Java QuickSelect Solution


  • -2
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            return findKthLargestRec(nums, 0, nums.length-1, k);
        }
        
        private int findKthLargestRec(int[] nums, int start, int end, int k) {
            int pIdx = partition(nums,start,end);
            if(k-1<pIdx)
                return findKthLargestRec(nums,start,pIdx-1,k);
            else if(k-1>pIdx)
                return findKthLargestRec(nums,pIdx+1,end,k);
            else
                return nums[k-1];
        }
        
        private int partition(int[] nums, int start, int end) {
            int pVal = nums[start]; // use random can save time in average
            swap(nums,start,end);
            int lo = start; int hi = end-1;
            while(lo<=hi) {
                while(lo<=end-1 && nums[lo]>pVal) {lo++;}
                while(hi>=start && nums[hi]<=pVal) {hi--;}
                if(lo<=hi)
                    swap(nums,lo++,hi--);
            }
            swap(nums,lo,end);
            return lo;
        }
        
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

  • 0
    J
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            return findKthLargestRec(nums, 0, nums.length-1, k);
        }
    
        private int findKthLargestRec(int[] nums, int start, int end, int k) {
            int pIdx = partition(nums,start,end);
            if(k-1<pIdx)
                return findKthLargestRec(nums,start,pIdx-1,k);
            else if(k-1>pIdx)
                return findKthLargestRec(nums,pIdx+1,end,k);
            else
                return nums[k-1];
        }
    
        private int partition(int[] nums, int start, int end) {
            int pVal = nums[start]; // use random can save time in average
            swap(nums,start,end);
            int lo = start; int hi = end-1;
            while(lo<=hi) {
                while(lo<=end-1 && nums[lo]>pVal) {lo++;}
                while(hi>=start && nums[hi]<=pVal) {hi--;}
                if(lo<=hi)
                    swap(nums,lo++,hi--);
                System.out.println("SWAP");
                for(int l = start; l <= end-1; l++)
                    System.out.print(nums[l] + ",");
                System.out.println();
            }
            swap(nums,lo,end);
            System.out.println("LAST SWAP");
            System.out.print("lo: " + lo);
            System.out.println();
            for(int l = start; l <= end-1; l++)
                System.out.print(nums[l] + ",");
            System.out.println();
            return lo;
        }
    
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    

    Please run this code. I don't think your partition is right because you write 【nums[hi]<=pVal】, though the result is right.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.