LeetCode LCR 076. 数组中的第 K 个最大元素

Categories:

题目描述
思路分析
1. 解法一：最小堆（推荐，稳定）
2. 解法二：快速选择（平均 O(n)）
相似题目

题目描述

✅ LCR 076. 数组中的第 K 个最大元素

思路分析

解法一：最小堆（推荐，稳定）

核心思路：

维护一个大小为 k 的最小堆，堆顶始终是当前 top-k 中最小的值。

遍历数组并入堆，若堆大小超过 k，弹出堆顶。

遍历结束后堆顶即第 k 大。

复杂度分析：

时间复杂度：O(n log k)，其中 n 表示数组长度。

空间复杂度：O(k)，其中 k 表示堆大小。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 最小堆，堆顶是当前 top-k 中最小值
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                // 超过 k 时弹出最小值
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}

// 定义最小堆
// heap.Interface 的方法都必须实现
// 这里用小顶堆维护 top-k
// 关键逻辑在 Push/Pop 与 Less
// 符合 Uber Go Style 的简洁实现

type MinHeap []int

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

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

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

func findKthLargest(nums []int, k int) int {
	h := &MinHeap{}
	heap.Init(h)

	// 将元素逐个加入堆，超过 k 时弹出最小值
	for _, num := range nums {
		heap.Push(h, num)
		if h.Len() > k {
			heap.Pop(h)
		}
	}

	return (*h)[0]
}

解法二：快速选择（平均 O(n)）

核心思路：

第 k 大等价于排序后下标为 n - k 的元素。

使用随机化 partition，pivot 落点为 p：若 p == n - k 直接返回，否则只递归一侧。

期望时间为线性。

复杂度分析：

时间复杂度：O(n)（平均），其中 n 表示数组长度。

空间复杂度：O(log n)，其中 log n 表示递归栈深度。

class Solution {
    private final Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickSelect(int[] nums, int left, int right, int index) {
        if (left == right) {
            return nums[left];
        }
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == index) {
            return nums[pivotIndex];
        }
        if (pivotIndex > index) {
            return quickSelect(nums, left, pivotIndex - 1, index);
        }
        return quickSelect(nums, pivotIndex + 1, right, index);
    }

    private int partition(int[] nums, int left, int right) {
        // 随机选择基准元素，避免退化
        int pivotIndex = random.nextInt(right - left + 1) + left;
        swap(nums, left, pivotIndex);
        int pivot = nums[left];

        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                nums[i++] = nums[j];
            }
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            if (i < j) {
                nums[j--] = nums[i];
            }
        }
        nums[i] = pivot;
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

func findKthLargest(nums []int, k int) int {
	return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(nums []int, left, right, index int) int {
	if left == right {
		return nums[left]
	}
	pivotIndex := partition(nums, left, right)
	if pivotIndex == index {
		return nums[pivotIndex]
	}
	if pivotIndex > index {
		return quickSelect(nums, left, pivotIndex-1, index)
	}
	return quickSelect(nums, pivotIndex+1, right, index)
}

func partition(nums []int, left, right int) int {
	// 随机选择基准元素，避免退化
	pivotIndex := rand.Intn(right-left+1) + left
	nums[left], nums[pivotIndex] = nums[pivotIndex], nums[left]
	pivot := nums[left]

	i, j := left, right
	for i < j {
		for i < j && nums[j] >= pivot {
			j--
		}
		if i < j {
			nums[i] = nums[j]
			i++
		}
		for i < j && nums[i] <= pivot {
			i++
		}
		if i < j {
			nums[j] = nums[i]
			j--
		}
	}
	nums[i] = pivot
	return i
}

相似题目

题目	难度	考察点
347. 前 K 个高频元素	中等	堆、哈希表
703. 数据流中的第 K 大元素	简单	堆
973. 最接近原点的 K 个点	中等	堆、快速选择
912. 排序数组	中等	排序
378. 有序矩阵中第 K 小的元素	中等	堆、二分
692. 前 K 个高频单词	中等	堆、哈希表
373. 查找和最小的 K 对数字	中等	堆
295. 数据流的中位数	困难	双堆
786. 第 K 个最小的素数分数	中等	堆、二分
1985. 找出数组中的第 K 大整数	中等	堆、快速选择

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/36999628