Partition thinking solution (quick sort) (JAVA)


  • 0
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            //we suppose 1<=k<=nums.length
            //so we don't need to check if nums == null
            return findK(nums, 0, nums.length - 1, k);
        }
        
        public int findK(int[] nums, int head, int tail, int k){
            int len = tail - head + 1;
            if(len == 1){
                return nums[head];
            }
            
            int i = head, j = tail - 1;
            //every time we select nums[tail] to do the partition
            //after partition left part < nums[tail], right part >= nums[tail]
            while(i <= j){
                while(nums[i] <= nums[tail]){ 
                    i++;
                    //all element <= nums[tail]
                    if(i == tail){
                        if(k == 1){
                            return nums[tail];
                        }
                        else{
                            return findK(nums, head, tail- 1, k - 1);
                        }
                    }
                }
                while(nums[j] > nums[tail]){ 
                    j--;
                    //all element > nums[tail]
                    if(j == head - 1){
                        if(k == len){
                            return nums[tail];
                        }
                        else{
                            return findK(nums, head, tail - 1, k);
                        }
                    }
                }
                if(i > j){
                    break;
                }
                //swap nums[i] and nums[j]
                nums[i] ^= nums[j];
                nums[j] ^= nums[i];
                nums[i] ^= nums[j];
                i++;
                j--;
            }
            //swap nums[i] and nums[tail]
            nums[i] ^= nums[tail];
            nums[tail] ^= nums[i];
            nums[i] ^= nums[tail];
            
            if(tail - i + 1 == k){
                return nums[i];
            }
            else if(tail - i + 1 < k){
                return findK(nums, head, i - 1, k - (tail - i + 1));
            }
            else{
                return findK(nums, i + 1, tail, k);
            }
        }
        
    }

Log in to reply
 

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