I am doubt why divide and conquer can not beat Max Heap way?


  • 0
    C

    This is my MaxHeap Way:

    public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        for(int i = (n - 1) / 2; i >= 0; i--)
           heapFixDown(nums, i, n);
        for(int i = n - 1; i >= n - k; i--){
            int tmp = nums[i];
            nums[i] = nums[0];
            nums[0] = tmp;
            heapFixDown(nums, 0, i);
        }
        return nums[n-k];
    }
    
    public void heapFixDown(int[] a, int i, int n){
    
        int j, tmp;
        tmp = a[i];
        j = 2 * i + 1; 
        while(j < n){
            if(j + 1 < n && a[j + 1] > a[j]) j++; 
            if(tmp >= a[j]) break; 
            a[i] = a[j]; 
            i = j; 
            j = j * 2 + 1;
        }
        a[i] = tmp;
    }}
    

    it runs 5ms and my divide and conquer way is:

    import java.util.Random;
    public class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        return findSubKthLargest(nums, 0, nums.length - 1, k);
        
    }
    
    public int findSubKthLargest(int[] nums, int start, int end, int k) {
        int splitPos = findPos(nums, start, end);
        if(splitPos == k - 1) return nums[k - 1];
        else if(splitPos > k - 1) return findSubKthLargest(nums, start, splitPos - 1, k);
        else return findSubKthLargest(nums, splitPos + 1, end, k);
    }
    
    public int findPos(int[] nums, int start, int end) {
        Random r = new Random();
        int f = r.nextInt(end - start + 1) + start;
        int p = nums[f];
        nums[f] = nums[start];
        int i = start;
        int j = end;
        while(i < j) {
            while(i < j && nums[j] < p) j--;
            if(i < j) nums[i++] = nums[j];
            while(i < j && nums[i] > p) i++;
            if(i < j) nums[j--] = nums[i];
        }
        nums[j] = p;
        return j;
    }}
    

    it runs 11ms.

    I consider divide and conquer way as O(N) but maxHeap way is O(KlogN). Why the result is in contrary?


Log in to reply
 

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