215. 数组中的第K个最大元素（JS实现）

缺乏、安全感 2022-11-25 13:19 72阅读 0赞

## 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 ≤ 数组的长度。

链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

## 2 思路 ##

**这道题考察排序，根据题意，选择堆排序比较合适**

## 3代码 ##

/** * @param {number[]} nums * @param {number} k * @return {number} */
    var findKthLargest = function(nums, k) { 
     if (nums.length <= 1) return nums[k-1] || null;
    
      nums.unshift(null);     //由于孩子节点的索引为父节点索引的2倍，因此为了计算方便数组第一项留空
      let len = Math.floor((nums.length-1) / 2);
    
      for (let i=len; i>=1; i--) { 
        adjust(i, nums.length-1);
      }
    
      for (let i=nums.length-1; i>=nums.length - k; i--) {    //找到第k大的数后，结束循环
        swap(1, i);
        adjust(1, i-1);
      }
    
      return nums[nums.length - k];
    
      function adjust(s, maxIndex) {     //调整不满足的子树结构使其符合大顶堆，s为需要调整的数
        let temp = nums[s];
    
        for (let i=2*s; i<=maxIndex; i*=2) {     //依次比较子节点，找到放置s的位置
          if (i+1 <= maxIndex && nums[i] < nums[i+1]) i++;
    
          if (temp > nums[i]) break;
    
          nums[s] = nums[i];
          s = i;
        }
    
        nums[s] = temp;
      }
    
      function swap(i,j) { 
        let temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
      }
    };