Deterministic O(n) solution using Divide and Conquer

• 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;
}
}
``````

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