【LeetCode 215】数组中的第K个最大元素

梦里梦外; 2022-12-04 07:53 141阅读 0赞

#### 题目描述 ####

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

#### 解题思路 ####

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

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

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

#### 代码实现 ####

/** * @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;
    }

#### 提交结果 ####

![在这里插入图片描述][20200906205731533.png]  
**快速排序：**  
![在这里插入图片描述][20200906213128273.png]

[20200906205731533.png]: /images/20221123/1d5ab4541aca4f18b4bca471b695f583.png?
[20200906213128273.png]: /images/20221123/73e4ea9592174ff2ab1725255b651eba.png?