AlgoViz Lab交互式算法学习
Algorithms first

数组中的第K个最大元素 · 交互式算法学习

返回数组第 k 大元素。

#215 · 堆

数组中的第K个最大元素

Kth Largest Element in an Array

测试用例nums = [3,2,1,5,6,4], k = 2
线性序列3 个关键状态
步骤 1目标升序下标为 4。target=4
3
0
2
1
1
2
5
3
6
4
4
5
推荐

快速选择

时间 平均 O(n)空间 O(1)

按枢轴分区，只继续包含目标下标的一侧。

1function findKthLargest(a, k) {2  const target = a.length - k;3  let l = 0,4    r = a.length - 1;5  while (true) {6    const p = a[r];7    let i = l;8    for (let j = l; j < r; j++)9      if (a[j] <= p)[a[i++], a[j]] = [a[j], a[i]];10    [a[i], a[r]] = [a[r], a[i]];11    if (i === target) return a[i];12    i < target ? l = i + 1 : r = i - 1;13  }14}
多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Solution {2    private int[] nums;3    private int k;4 5    public int findKthLargest(int[] nums, int k) {6        this.nums = nums;7        this.k = nums.length - k;8        return quickSort(0, nums.length - 1);9    }10 11    private int quickSort(int l, int r) {12        if (l == r) {13            return nums[l];14        }15        int i = l - 1, j = r + 1;16        int x = nums[(l + r) >>> 1];17        while (i < j) {18            while (nums[++i] < x) {19            }20            while (nums[--j] > x) {21            }22            if (i < j) {23                int t = nums[i];24                nums[i] = nums[j];25                nums[j] = t;26            }27        }28        if (j < k) {29            return quickSort(j + 1, r);30        }31        return quickSort(l, j);32    }33}
交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。
动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。
适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。
AlgoViz Lab

数组中的第K个最大元素 · 解法对比

AlgoViz Lab

返回数组第 k 大元素。

测试用例
nums = [3,2,1,5,6,4], k = 2
题目分类
堆
解法对比
2
方案 1

完整排序

升序排序后读取倒数第 k 项。

时间
O(n log n)
空间
O(log n)
方案 2

快速选择

按枢轴分区，只继续包含目标下标的一侧。

时间
平均 O(n)
空间
O(1)