Median of Median - Worst case linear time O(n) - 8ms


  • 0
    N
    public class Solution {
       public int findMedian(int [] arr,int l,int r){
    		Arrays.sort(arr,l,r);
    		return arr[l+(r-l)/2];
    	}
    	
    	public void swap(int [] arr,int i,int j){
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] =temp;
    	}
    	public int partition(int [] arr,int l,int r,int key){
    		int i = l;
    		for(i=l;i<r;i++){
    			if(arr[i] == key)
    				break;
    		}
    		swap(arr,i,r);
    		i=l;
    		for(int j=l;j<r;j++){
    			if(arr[j]>key){
    				
    				swap(arr,i,j);
    				i++;
    			}
    		}
    		swap(arr,i,r);
    		return i;
    	}
    	public  int kthlargest(int [] arr,int l,int r,int k){
    		if(k>0 && k<=(r-l+1)){
    			int n = r-l+1;
    			int [] median = new int[(n+4)/5];
    			int i=0;
    			for(i=0;i<n/5;i++){
    				median[i] = findMedian(arr,l+i*5,l+i*5+5);
    			}
    	
    			if(n%5!=0){
    				median[i] = findMedian(arr,l+i*5,l+i*5+n%5);
    				i++;
    			}
    			int medofmed = (i==1)?median[0]:kthlargest(median,0,i-1,i/2);
    			int pos = partition(arr,l,r,medofmed);
    			if(pos-l == k-1)
    				return arr[pos];
    			if(k-1 < pos-l){
    				return kthlargest(arr,l,pos-1,k);
    			}
    			else
    				return kthlargest(arr,pos+1,r,k-pos+l-1);
    		}
    		return Integer.MAX_VALUE;
    	}
        
        public int findKthLargest(int[] nums, int k) {
            
            if(nums.length==1 && k==1)
                return nums[0];
            
            return kthlargest(nums,0,nums.length-1,k);
        
            
        }
    }
    

    Similar to quick select but selects pivot in a balanced way.


Log in to reply
 

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