Pengjielee's blog

题目

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

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
解释：排序后：1,2,3,4,5,6，第2大元素是5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
解释：排序后：1,2,2,3,3,4,5,5,6，第4大元素是4

说明:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、暴力解法

使用内置函数sort函数实现；
把元素从大到小排序，然后返回下标为k-1的元素。

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

2、快速选择

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 交换函数
function swap(array, a, b) {
  const temp = array[a];
  array[a] = array[b];
  array[b] = temp;
}

// 分区函数
function partition(array, left, right, pivot_index) {
  // 使用变量存储轴值
  let pivot = array[pivot_index];
  // 1. 把轴值移到最右边
  swap(array, pivot_index, right);
  // 分区下标（从左边开始）
  let store_index = left;

  // 2. 把所有比轴值小的移到左边
  for (let i = left; i <= right; i++) {
    if (array[i] < pivot) {
      swap(array, store_index, i);
      store_index++;
    }
  }

  // 3. 交换轴值到最终位置
  swap(array, store_index, right);

  // 返回分区下标
  return store_index;
}

// 快速选择
var quickSelect = function (nums, left, right, k_smallest) {
  if (left == right) {
    return nums[left];
  }

  // 生成随机下标
  let pivot_index = left + parseInt(Math.random() * (right - left), 10);

  // 获取分区后的下标
  pivot_index = partition(nums, left, right, pivot_index);

  if (k_smallest == pivot_index) {
    return nums[k_smallest];
  } else if (k_smallest < pivot_index) {
    return quickSelect(nums, left, pivot_index - 1, k_smallest);
  } else {
    return quickSelect(nums, pivot_index + 1, right, k_smallest);
  }
};

var findKthLargest = function (nums, k) {
  const size = nums.length;
  return quickSelect(nums, 0, size - 1, size - k);
};