Iterative and in-place quickselect, short solution in Java


  • 0
    S

    Most solutions are recursive. There is a iterative in-place solution, it actually easier as we don't need to adjust k each time.

    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            int start = 0, end = nums.length -1;
            while(start < end){
                int loc = start;
                for(int i=start; i<end; i++){
                    if(nums[i] > nums[end]){
                        swap(nums, loc, i);
                        loc++;
                    }
                }
                swap(nums, loc, end);
                if(loc == k-1)
                    return nums[loc];
                else if(loc >= k)
                    end = loc-1;
                else
                    start = loc+1;
            }
            return nums[start];
        }
        
        private void swap(int[] nums, int a, int b){
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
    }

  • 0

    For posterity, this method uses the Lomuto partitioning scheme. A faster O'Hare partitioning scheme exists, though.


Log in to reply
 

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