README.md

数组中的第k个最大元素

难度：中等

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

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

 

示例

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解题

暴力解法

/**
 * 暴力解法
 * @时间复杂度 O(NlogN)  空间复杂度 O(1)
 * @param nums
 * @param k
 * @returns
 */
export function findKthLargest(nums: number[], k: number): number {
  nums.sort((a, b) => b - a)
  return nums[k - 1]
}

快速排序

/**
 * 快速排序
 * @desc 时间复杂度 O(N)  空间复杂度 O(logN)
 * @param nums
 * @param k
 * @returns
 */
export function findKthLargest2(nums: number[], k: number): number {
  quickSort(nums, 0, nums.length - 1, k)
  return nums[k - 1]

  function quickSort(nums: number[], left: number, right: number, k: number) {
    if (left < k && left < right) {
      const partitonIndex = partition(nums, left, right)
      quickSort(nums, left, partitonIndex - 1, k)
      quickSort(nums, partitonIndex + 1, right, k)
    }
  }

  function partition(nums: number[], left: number, right: number): number {
    const pivot = left
    let idx = pivot + 1
    for (let i = idx; i <= right; i++) {
      if (nums[i] > nums[pivot]) {
        [nums[i], nums[idx]] = [nums[idx], nums[i]]
        idx++
      }
    }

    [nums[pivot], nums[idx - 1]] = [nums[idx - 1], nums[pivot]]
    return idx - 1
  }
}