LeetCode215. 数组中的第K个最大元素🌟🌟🌟🌟中等

算法系统课免费

课后作业

问题描述

原文链接：215. 数组中的第K个最大元素

给定整数数组 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 <= 105
-104 <= nums[i] <= 104

代码实现

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {

        // 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
        Queue<Integer> minQueue = new PriorityQueue<>();
        for(int i = 0 ; i < nums.length; i++){
            if(minQueue.size() < k){
                minQueue.offer(nums[i]);
            }else if(minQueue.peek() < nums[i]){
                minQueue.poll();
                minQueue.offer(nums[i]);
            }
        }

        return minQueue.peek();
    }
}

Python

import heapq

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
        min_heap = []
        for num in nums:
            if len(min_heap) < k:
                heapq.heappush(min_heap, num)
            elif min_heap[0] < num:
                heapq.heappushpop(min_heap, num)

        return min_heap[0]

C++

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
        std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
        for (int num : nums) {
            if (min_heap.size() < k) {
                min_heap.push(num);
            } else if (min_heap.top() < num) {
                min_heap.pop();
                min_heap.push(num);
            }
        }

        return min_heap.top();
    }
};

Go

func findKthLargest(nums []int, k int) int {
    // 默认是小根堆 复杂度 空间：O(k). 时间 nlogk
    minHeap := &IntMinHeap{}
    heap.Init(minHeap)

    for _, num := range nums {
        if minHeap.Len() < k {
            heap.Push(minHeap, num)
        } else if (*minHeap)[0] < num {
            heap.Pop(minHeap)
            heap.Push(minHeap, num)
        }
    }

    return (*minHeap)[0]
}

type IntMinHeap []int

func (h IntMinHeap) Len() int           { return len(h) }
func (h IntMinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntMinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntMinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntMinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minQueue = new PriorityQueue<>(); for (int i = 0 ; i < nums.length; i ++) { if (minQueue.size() < k) { minQueue.offer(nums[i]); } else if (minQueue.peek() <= nums[i]) { minQueue.poll(); minQueue.offer(nums[i]); } } return minQueue.peek(); } }

//法一：堆排序 class Solution { public int findKthLargest(int[] nums, int k) { //建立小顶堆 PriorityQueue pq = new PriorityQueue<>((x, y) -> Integer.compare(x, y)); for(int i = 0; i < nums.length; i++){ pq.offer(nums[i]); if(pq.size() > k){ pq.poll(); } } return pq.peek(); } } //法二：快排 class Solution { public int findKthLargest(int[] nums, int k) { shuffle(nums); int l = 0; int r = nums.length - 1; k = nums.length - k;//转换成排名第k的元素 while(l <= r){ int index = partition(nums, l, r); if(index < k){ l = index + 1; }else if(index > k){ r = index - 1; }else{ return nums[index]; } } return 0; } /* 哨兵划分 */ private static int partition(int[] nums, int left, int right) { // 以 nums[left] 作为基准数 int i = left, j = right; while (i < j) { while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素 while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素 swap(nums, i, j); // 交换这两个元素 } swap(nums, i, left); // 将基准数交换至两子数组的分界线 return i; // 返回基准数的索引 } /* 元素交换 */ private static void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } // 洗牌算法，将输入的数组随机打乱 private static void shuffle(int[] nums) { Random rand = new Random(); int n = nums.length; for (int i = 0 ; i < n; i++) { // 生成 [i, n - 1] 的随机数 int r = i + rand.nextInt(n - i); swap(nums, i, r); } } }

LeetCode215. 数组中的第K个最大元素🌟🌟🌟🌟中等

课后作业

问题描述

代码实现

Java

Python

C++

Go

发表回复取消回复

评论(3)

课后作业

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(3)

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复