Java Randomized Select Algorithm


  • 0
    Z
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            return randomizedSelect(nums, 0, nums.length-1, nums.length - k + 1);
        }
        
        public int randomizedSelect(int[] nums, int p, int r, int i){
            if(p == r)
                return nums[p];
            int q = randomizedPartition(nums, p, r);
            int k = q - p + 1;
            if(i == k)          // the pivot value is the answer
                return nums[q];
            else if (i < k)
                return randomizedSelect(nums, p, q - 1, i);
            else 
                return randomizedSelect(nums, q + 1, r, i - k);
        }
        
        public int randomizedPartition(int[] nums, int p, int r){
            Random rand = new Random();
            int i = p + rand.nextInt(r-p+1);
            swap(nums, i, r);
            return partition(nums, p, r);
        }
        
        public int partition(int[] nums, int p, int r){
            int x = nums[r];
            int i = p - 1;
            for(int j = p; j < r; j++){
                if(nums[j] <= x){
                    i = i + 1;
                    swap(nums, i, j);
                }
            }
            swap(nums, i+1, r);
            return i+1;
        }
        
        public void swap(int[] nums, int i, int j){
            int swap = nums[j];
            nums[j] = nums[i];
            nums[i] = swap;
        }
    }
    

Log in to reply
 

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