215.Kth Largest Element in an Array

tags: `Medium` `Array` `Divide and Conquer` `Sorting` `Heap`

題目描述

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Can you solve it without sorting?

範例

Example 1:

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

Example 2:

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

Constraints:

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

解答

Python







class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        data = nums[:k]
        heapq.heapify(data)
        for num in nums[k:]:
            heapq.heappushpop(data, num)
        return min(data)

Yen-Chi ChenMon, Aug 14, 2023

TypeScript

quick select

partition 函式會回傳一個 pivot，這個 pivot 左邊的元素都比 pivot 大，右邊的元素都比 pivot 小，不斷呼叫 partition 然後每次檢查 pivot 的位置是否為 k - 1，如果是的話就回傳 pivot 的值。

function partition(arr: number[], left: number, right: number) {
  const pivot = arr[right];
  while (left < right) {
    while (left < right && arr[left] >= pivot) {
      left++;
    }
    arr[right] = arr[left];
    while (left < right && arr[right] <= pivot) {
      right--;
    }
    arr[left] = arr[right];
  }
  arr[right] = pivot;
  return left;
}

function findKthLargest(nums: number[], k: number): number {
  let low = 0;
  let high = nums.length - 1;
  let pivot = partition(nums, low, high);

  while (pivot !== k - 1) {
    if (pivot > k - 1) {
      high = pivot - 1;
      pivot = partition(nums, low, high);
    } else {
      low = pivot + 1;
      pivot = partition(nums, low, high);
    }
  }

  return nums[pivot];
}

counting sort

function findKthLargest(nums: number[], k: number): number {
  const n = nums.length;
  let max = nums[0];
  let min = nums[0];

  for (const num of nums) {
    if (num > max) {
      max = num;
    }
    if (num < min) {
      min = num;
    }
  }

  const size = max - min + 1;
  const buckets = new Array(size).fill(0);
  for (let i = 0; i < n; i++) {
    buckets[nums[i] - min]++;
  }

  let remain = k;
  for (let i = size - 1; i >= 0; i--) {
    remain -= buckets[i];
    if (remain <= 0) {
      return i + min;
    }
  }

  return -1;
}

SheepMon, Aug 14, 2023

C++













class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> kthFinder;
        for (int num : nums) {
            kthFinder.push(num);
            while (kthFinder.size() > k) {
                kthFinder.pop();
            }
        }
        return kthFinder.top();
    }
};

Jerry Wu14 Aug 2023

Reference

回到題目列表