215. 数组中的第K个最大元素

1. 题目描述

在未排序的数组中找到第 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

说明：你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

2. 解题思路

最直接的思路就是对数组进行排序，然后直接返回排序后数组的倒数第k个元素。

除了使用sort()方法直接对数组进行排序之外，我们还可以使用快速排序对数组进行排序操作。正好也来复习一下快速排序算法。

我们知道数组从小到大排序之后，第K大元素就是索引为n-k的的值，那么n-k之前的值都比他小，n-k之后的值都比他大。我们可以把 n-k 看作 pivot ，之后用快速排序来解答。

3. 代码实现

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let res = nums.sort((a,b) => a-b)
    return res[res.length - k]
};

快速排序：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const findKthLargest = (nums, k) => {
  const n = nums.length;
  const quick = (l, r) => {
    if (l > r) return;
    let random = Math.floor(Math.random() * (r - l + 1)) + l; // 随机选取一个index
    swap(nums, random, r);  // 将它和位置r的元素交换，让 nums[r] 作为 pivot 元素
    // 选定一个 pivot 元素，根据它进行分区。让左边的元素都比pivot小，右边的元素都比pivot大
    let pivotIndex = partition(nums, l, r);
    // 希望pivotIndex 正好是 n-k，如果小于他，则再其左边继续查找，如果大于他，就在其右边继续查找
    if (n - k < pivotIndex) { 
      quick(l, pivotIndex - 1);
    } else {
      quick(pivotIndex + 1, r);
    }
  };
  quick(0, n - 1); 
  return nums[n - k]; 
};
function partition(nums, left, right) {
  let pivot = nums[right];            
  let pivotIndex = left; 
  // 遍历数组，和pivot进行比较，如果比他小，就将他换到pivotIndex的位置              
  for (let i = left; i < right; i++) { 
    if (nums[i] < pivot) {            
      swap(nums, i, pivotIndex);      
      pivotIndex++;                    
    }
  }
  // 循环结束之后， pivotIndex左边都是比pivot小的数，让其与right交换，更新pivot元素                                  
  swap(nums, right, pivotIndex);     
  return pivotIndex;                  
}
// 交换函数
function swap(nums, p, q) {
  const temp = nums[p];
  nums[p] = nums[q];
  nums[q] = temp;
}

4. 提交结果

快速排序：