【Day 85 】2024-07-01 - 215. 数组中的第 K 个最大元素

[azl397985856]

215. 数组中的第 K 个最大元素

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/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 ≤ 数组的长度。

[xy147]

js代码

var findKthLargest = function(nums, k) {
   let heapSize=nums.length
    buildMaxHeap(nums,heapSize)
    for(let i=nums.length-1;i>=nums.length-k+1;i--){
        swap(nums,0,i)
        --heapSize
         maxHeapify(nums, 0, heapSize);
    }
    return nums[0]
   function buildMaxHeap(nums,heapSize){
     for(let i=Math.floor(heapSize/2)-1;i>=0;i--){
        maxHeapify(nums,i,heapSize)
     }
   }
   function maxHeapify(nums,i,heapSize){
       let l=i*2+1
       let r=i*2+2
       let largest=i
       if(l < heapSize && nums[l] > nums[largest]){
           largest=l
       }
       if(r < heapSize && nums[r] > nums[largest]){
           largest=r
       }
       if(largest!==i){
           swap(nums,i,largest)
           maxHeapify(nums,largest,heapSize)
       }
   }
   function swap(a,  i,  j){
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
   }
};

复杂度分析

时间复杂度：O(nlogn) 空间复杂度：O(logn)

[luzhaofeng]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        pq = []   
        for num in nums:
            heapq.heappush(pq, num) # 当前元素入堆
            if len(pq) > k:
                heapq.heappop(pq)   # 堆中元素超过k个，弹出最小的那个
        return pq[0]

[franklinsworld666]

代码

from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap_size = len(nums)
        self.build_max_heap(nums, heap_size)

        for i in range(len(nums)-1, len(nums)-k, -1):
            nums[0], nums[i] = nums[i], nums[0]
            heap_size -= 1
            self.max_heapify(nums, 0, heap_size)
        return nums[0]

    def build_max_heap(self, nums, heap_size):
        for i in range(heap_size // 2, -1, -1):
            self.max_heapify(nums, i, heap_size)

    def max_heapify(self, nums, i, heap_size):
        left = i * 2 + 1
        right = i * 2 + 2
        largest = i
        if left < heap_size and nums[left] > nums[largest]:
            largest = left
        if right < heap_size and nums[right] > nums[largest]:
            largest = right
        if (largest != i):
            nums[i], nums[largest] = nums[largest], nums[i]
            self.max_heapify(nums, largest, heap_size)

[CathyShang]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        a = []   
        for num in nums:
            heapq.heappush(a, num)
            if len(a) > k:
                heapq.heappop(a)   
        return a[0]

[Dtjk]

class Solution { public: int findKthLargest(vector& nums, int k) { priority_queue<int,vector,greater> pq; for(auto n:nums){ if(pq.size()==k && pq.top() >= n)continue; if(pq.size()==k){ pq.pop(); } pq.push(n); } return pq.top(); } };

[hillsonziqiu]

思路

快排

代码

// @lc code=start
/*
 * @lc app=leetcode.cn id=215 lang=javascript
 *
 * [215] 数组中的第K个最大元素
 */
function partition(nums, left, right) {
  let pivot = nums[right];
  let pivotIndex = left;
  for (let i = left; i < right; i++) {
    if (nums[i] < pivot) {
      swap(nums, i, pivotIndex);
      pivotIndex++;
    }
  }
  swap(nums, right, pivotIndex);
  return pivotIndex;
}

function swap(nums, p, q) {
  const temp = nums[p];
  nums[p] = nums[q];
  nums[q] = temp;
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const n = nums.length;

  const quick = (l, r) => {
    if (l > r) return;
    let random = Math.floor(Math.random() * (r - l + 1)) + l;
    swap(nums, random, r);
    let pivotIndex = partition(nums, l, r);

    if (n - k < pivotIndex) {
      quick(l, pivotIndex - 1);
    } else {
      quick(pivotIndex + 1, r);
    }
  };

  quick(0, n - 1); 
  return nums[n - k];
};
// @lc code=end

[zhiyuanpeng]

import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if len(nums) == 1:
            return nums[0]
        # find the pivot index len(nums) - k
        target = len(nums) - k
        ans = self.findKthLargestHelper(nums, 0, len(nums)-1, target)
        return ans

    def findKthLargestHelper(self, nums, start, end, k):
        if start == end:
            return nums[start]
        else:
            index = self.partition(nums, start, end)
            if index == k:
                return nums[index]
            elif index > k:
                return self.findKthLargestHelper(nums, start, index-1, k)
            else:
                return self.findKthLargestHelper(nums, index+1, end, k)

    def partition(self, nums, start, end):
        pivot_index = random.randint(start, end)
        pivot = nums[pivot_index]
        l, r = start, end + 1
        nums[start], nums[pivot_index] = pivot, nums[start]
        while True:
            while True:
                l += 1
                if l == end or nums[l] >= pivot:
                    break
            while True:
                r -= 1
                if r == start or nums[r] <= pivot:
                    break
            if l >= r:
                break
            nums[l], nums[r] = nums[r], nums[l]
        nums[start], nums[r] = nums[r], nums[start]
        return r