215. Kth Largest Element in an Array

Description

Here

Intuition

这道题首先有O(NLogK)的solution，非常明显。然而，我们可以做的更好。

在merge sort中有一个partition，可以在O(N)地将一个数组分成两个部分，一边大，一边小。

这样，我们就可以决定哪边会有我们的target。

Time Complexity = n + n/2 + n/4 + n/8 + ... + 1 = n (1 + 1/2 + 1/4 + 1/8 + ... ) ≈ 2 n --refernce

Solution

Key idea to implement such a function:

1. choose the most right index as the pivot value
2. keep an pointer storeIndex to track the max sorted to go.
3. sweep from left to right

  /**
   * Left part will be less than or equals to pivot value, right will be greater than.
   *
   * @param nums
   * @param left
   * @param right
   * @return
   */
  int partition(int[] nums, final int left, final int right) {
    // choose the right one as pivot
    // if not, choose any one, and swap to the right;

    int pivot = nums[right];
    int storeIndex = left;
    for (int i = left; i < right; i++) {
      if (nums[i] <= pivot) {
        swap(nums, i, storeIndex);
        storeIndex++;
      }
    }
    swap(nums, storeIndex, right);
    return storeIndex;
  }

Full Solution