215.Kth-Largest-Element-in-an-Array

215. Kth Largest Element in an Array

题目地址

https://leetcode.com/problems/kth-largest-element-in-an-array/

题目描述

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

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

Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

代码

Approach #0 Sort

class Solution {
  public int findKthLargest(int[] nums, int k) {

  }
}

Approach #1 Heap

class Solution {
  public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
    for (int n: nums) {
      heap.add(n);
      if (heap.size() > k) {
        heap.poll();
      }
    }

    return heap.poll();
  }
}

Approach #2 Quickselect

class Solution {
    int[] nums;
    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        int size = nums.length;

        return quickselect(0, size - 1, size - k);
    }

    private int quickselect(int left, int right, int k) {
        if (left == right)  return nums[left];

        int index = left + (right - left) / 2;
        index = partition(left, right, index);

        if (k == index) {
            return nums[k];
        } else if (k < index) {
            return quickselect(left, index - 1, k);
        } else {
            return quickselect(index + 1, right, k);
        }
    }

    private int partition(int left, int right, int index) {
        int pivot = nums[index];
        // 1. move pivot to end
        swap(index, right);

        // 2. move all smaller elements to the left
        int start = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(start, i);
                start++;
            }
        }

        // 3. move pivot to its final place
        swap(start, right);

        return start;
    }

    private void swap(int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}