215. 数组中的第K个最大元素 (opens new window)

Description

Difficulty: 中等

Related Topics: 数组 (opens new window), 分治 (opens new window), 快速选择 (opens new window), 排序 (opens new window), 堆（优先队列） (opens new window)

给定整数数组 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⁵
• -10⁴ <= nums[i] <= 10⁴

Solution

Language: JavaScript

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

var findKthLargest = function (nums, k) {
  for (let i = nums.length; i > nums.length - k - 1; i--) {
    for (let j = 0; j < i; j++) {
      if (nums[j] > nums[i]) {
        [nums[j], nums[i]] = [nums[i], nums[j]]
      }
    }
  }
  return nums[nums.length - k]
};


// 最大堆
function swap(arr, i ,j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j]= temp;
}

function heapify(arr, x, length) {
    var l = 2*x+1;
    var r = 2*x+2;
    var largest = x;
    if(l<length && arr[l] > arr[largest]) {
        largest = l;
    }
    if(r<length && arr[r] > arr[largest]) {
        largest = r;
    }
    if(largest!= x) {
        swap(arr, x, largest);
        // 递归交换以下的是否也建好堆.
        heapify(arr, largest, length);
    }
}

var findKthLargest = function(nums, k) {
    var size = nums.length;
    // 建立堆
    for(var i = parseInt(size/2)+1 ; i >=0 ;i --) {
        heapify(nums, i, size);
    }
    // 排序
    for(var j= size-1; j>=size-k; j--) {
        // 得到本次的最大，将最大的与最后一个交换位子
        swap(nums, 0, j);
        heapify(nums, 0, j);
    }
    return nums[size-k];
}