-1

I came across kth largest number problem in Leetcode

Input: [3,2,1,5,6,4] and k = 2, Output: 5

Suggested Solution:

 public int findKthLargest(int[] nums, int k) {
    shuffle(nums);
    k = nums.length - k;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
        final int j = partition(nums, lo, hi);
        if(j < k) {
            lo = j + 1;
        } else if (j > k) {
            hi = j - 1;
        } else {
            break;
        }
    }
    return nums[k];
}

private int partition(int[] a, int lo, int hi) {

    int i = lo;
    int j = hi + 1;
    while(true) {
        while(i < hi && less(a[++i], a[lo]));
        while(j > lo && less(a[lo], a[--j]));
        if(i >= j) {
            break;
        }
        exch(a, i, j);
    }
    exch(a, lo, j);
    return j;
}

private void exch(int[] a, int i, int j) {
    final int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

private boolean less(int v, int w) {
    return v < w;
}

Doesn't partition take O(n) and the while loop in the main function take O(log n) so it should be O(nlog n)? This looks like it uses Quicksort but the runtime for quicksort is O(nlogn). If quicksort takes O(n), this makes sense but it does not. Please help me understand what is going on?

k_ssb
  • 6,024
  • 23
  • 47
Matt Choi
  • 169
  • 1
  • 13
  • 1
    This wikipedia reference might help: [Quickselect](https://en.wikipedia.org/wiki/Quickselect) – Blastfurnace Jun 20 '18 at 01:49
  • wow, never even knew this existed.. shame on me for my 4 years of CS degree.. – Matt Choi Jun 20 '18 at 01:51
  • 1
    Possible duplicate of [How to find the kth largest element in an unsorted array of length n in O(n)?](https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on) – Blastfurnace Jun 20 '18 at 01:53

1 Answers1

3

This is a randomized algorithm that has average/expected O(n) runtime. This is because after randomly shuffling the input list, we typically have pivots good enough to expect that after each partition function call if we don't find the target yet we reduce our list (to be search next) roughly by half. This means even though if we not lucky and have to continuously call partition function we continuously keep reducing our list's size by half, therefore the average runtime is still only O(n) since O(n) + O(n/2) + O(n/4) + ... + O(1) is still O(n).

user2760845
  • 124
  • 5