215.Kth_Largest_Element_in_an

Time Flying

标签

Edit in GitHub

215.Kth Largest Element in an Array

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

解题

解法一: 排序。空间复杂度为 O(NlogN), 空间复杂度为 O(1)

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

如果初始数据的元素个数不确定, 解法一就无法使用了, 这个时候适合使用解法二。

解法二: 快速选择

思路: 本方法大致上与快速排序相同。简便起见，注意到第 k 个最大元素也就是升序排序后下标为 N - k 的元素。递归使用划分算法。

使用划分算法, 定义一个枢纽值, 并将其放到指定位置(小于该枢纽值的都在其左边, 大于该枢纽值的都在其右边);
比较枢纽值的下标 position 与 N - k 的大小关系

算法复杂度为 O(n)。计算: n + (1/2) * n + (1/4) * n + ... + (1/2)^n * n, 经等比数列求和为 2n - 2n / 2^n, 当 n 趋于无穷大时, 结果趋近为 2n。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  const length = nums.length
  return quickSelect(0, length - 1, length - k, nums)
}

var quickSelect = function(left, right, kthSmall, arr) {
  const position = partition(arr, left, right)
  if (position === kthSmall) {
    return arr[position]
  } else if (position < kthSmall) {
    return quickSelect(position + 1, right, kthSmall, arr)
  } else if (position > kthSmall) {
    return quickSelect(left, position - 1, kthSmall, arr)
  }
}

/* 分区算法 */
function partition(nums, left, right) {
  const pivot = nums[left] // 枢纽值
  let pos = left           // 用来记住最后枢纽值 pivot 应该置于的位置
  for (let i = left + 1; i <= right; i++) {
    if (nums[i] < pivot) {
      pos++
      swap(nums, pos, i)
    }
  }
  swap(nums, pos, left)
  return pos
}

/* 交换位置
  nums 数组, a, b 为下标
*/
var swap = function(nums, a, b) {
  const tmp = nums[a]
  nums[a] = nums[b]
  nums[b] = tmp
}

215.Kth Largest Element in an Array

解题

镜像题目