Deterministic O(n) solution using Divide and Conquer


  • 0
    Z

    Using buckets to select the "median of medians" which can accelerate the efficiency of divide and conquer

      public class Solution {
          public int findKthLargest(int[] nums, int k) {
            return select(k,nums,0,nums.length-1);
        }
        public int select(int k, int[] nums,int l, int r){
            if(k>nums.length||k<1)return -1;
            int length = r - l +1;
            if(length<=5){
                Arrays.sort(nums,l,r+1);
                return nums[r - k+1];
            }
            
            int i = l;
            int size = length%5==0?length/5:length/5+1;
            int[] S = new int[size];
            int p = 0;
            while(i<=r){
                int left = i;
                int right = i+4<=r?i+4:r;
                int median = (right - left)/2 + 1;
                S[p++] = select(median,nums,left,right);
                i += 5;
            }
    
            int start = l, end = r;
            i = l;
            int L1=0,M=0,L2=0;
            int m = select(S.length%2==0?S.length/2:S.length/2+1,S,0,S.length-1);
            while(i<=r){
                if(nums[i]<m){L1++;exch(nums,i++,l++);}
                else if(nums[i]>m){L2++;exch(nums,i,r--);}
                else if(nums[i]==m){M++;i++;}
            }
            //select
            if(L2>=k){
                return select(k,nums,i,end);
            }
            else if(L2+M<k){
                return select(k-L2-M,nums,start,l-1);
            }
            return m;
        }
        private static void exch(int[] a, int i, int j) {
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    }
    

Log in to reply
 

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