数组中第 K 大的元素

数组中第 K 大的元素

问题

这个题目说的是，给你一个整数数组和一个整数 K，你要找到数组中第 K 大的元素。

比如说，给你的整数数组是：

4, 2, 8, 1, 8

整数 K 是 2。这个数组中第 2 大的元素是 8，因此你要返回 8。

代码

public class AlgoCasts {

  // Time: O(n*log(k)), Space: O(k)
  public int findKthLargestMinHeap(int[] nums, int k) {
    Queue<Integer> minHeap = new PriorityQueue<>();
    for (int num: nums) {
      if (minHeap.size() < k) {
        minHeap.add(num);
      } else if (num > minHeap.peek()) {
        minHeap.poll();
        minHeap.add(num);
      }
    }
    return minHeap.peek();
  }

  void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }

  int partition(int[] nums, int low, int high) {
    int pivot = nums[low], i = low, j = high;
    while (i < j) {
      while (i < j && nums[j] < pivot) --j;
      if (i < j) swap(nums, i, j);
      while (i < j && nums[i] >= pivot) ++i;
      if (i < j) swap(nums, i, j);
    }
    return i;
  }

  // Time(avg): O(n), Time(worst): O(n^2), Space: O(1)
  public int findKthLargestQuickSelect(int[] nums, int k) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
      int p = partition(nums, low, high);
      if (p == k-1) return nums[p];
      else if (p > k-1) high = p - 1;
      else low = p + 1;
    }
    return -1;
  }

}