LeetCode-热题100：215. 数组中的第K个最大元素

题目描述

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

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

代码及注释

func findKthLargest(nums []int, k int) int {
    // 使用快速选择算法找到数组中第 k 大的元素
    return quickSelect(nums, 0, len(nums) - 1, len(nums) - k)
}

func quickSelect(nums []int, left, right, k int) int {
    // 当左边索引等于右边索引时，返回当前元素作为第 k 大的元素
    if left == right {
        return nums[k]
    }

    // 选择最左边的元素作为基准值
    index := nums[left]

    // 初始化两个指针 i 和 j
    i := left - 1
    j := right + 1

    // 开始分区过程
    for i < j {
        // 从左往右找到第一个大于等于基准值的元素
        for i++; nums[i] < index; i++ {}
        // 从右往左找到第一个小于等于基准值的元素
        for j--; nums[j] > index; j-- {}
        
        // 交换两个元素的位置
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }

    // 如果 k 小于等于 j，则在左侧继续查找
    if k <= j {
        return quickSelect(nums, left, j, k)
    } else {
        // 否则，在右侧继续查找
        return quickSelect(nums, j + 1, right, k)
    }
}

代码解释

快速选择算法（Quick Select）：

快速选择算法是快速排序算法的一个变种，它的主要思想是选择一个基准值（pivot），然后将数组分为两部分：一部分的所有元素都大于基准值，另一部分的所有元素都小于基准值。如果基准值的位置恰好是第 k 大的元素，那么这个基准值就是我们要找的结果；如果不是，我们可以根据基准值的位置进一步缩小查找范围。

findKthLargest 函数：

func findKthLargest(nums []int, k int) int {
    // 使用快速选择算法找到数组中第 k 大的元素
    return quickSelect(nums, 0, len(nums) - 1, len(nums) - k)
}

在 findKthLargest 函数中，我们调用 quickSelect 函数来找到第 k 大的元素。由于数组的索引是从 0 开始的，所以我们需要找的是 len(nums) - k 位置的元素。

在 quickSelect 函数中：

1. 首先，选择最左边的元素作为基准值 index。

   index := nums[left]
   

2. 使用两个指针 i 和 j 分别从左到右和从右到左进行扫描，找到第一个大于等于基准值的元素和第一个小于等于基准值的元素，然后交换它们的位置。

   i := left - 1
   j := right + 1
   
   for i < j {
       for i++; nums[i] < index; i++ {}
       for j--; nums[j] > index; j-- {}
       if i < j {
               nums[i], nums[j] = nums[j], nums[i]
       }
   }
   

3. 根据基准值的位置 j 和 k 的值来决定是在左侧还是右侧继续递归查找。

   if k <= j {
       return quickSelect(nums, left, j, k)
   } else {
       return quickSelect(nums, j + 1, right, k)
   }
   

为什么要这样做？

快速选择算法的核心思想是分治法，它能够快速地找到一个数组中第 k 大的元素，而不需要对整个数组进行完全的排序。通过不断地缩小查找范围，每次都能排除掉一半的元素，从而大大提高了查找效率。

在这个实现中，我们选择最左边的元素作为基准值，然后通过两个指针 i 和 j 从两端开始扫描，找到第一个大于等于基准值的元素和第一个小于等于基准值的元素，然后交换它们的位置。这样，数组就被分成了两部分：一部分的所有元素都大于基准值，另一部分的所有元素都小于基准值。

接着，我们根据基准值的位置 j 和 k 的值来决定是在左侧还是右侧继续递归查找。如果 k <= j，则在左侧继续查找；否则，在右侧继续查找。这样，每次递归调用都能将查找范围缩小一半，从而大大提高了查找效率。

综上所述，这段代码通过快速选择算法高效地找到了一个整数数组中第 k 大的元素，其时间复杂度为 (O(n))，其中 (n) 是数组的长度。