数组中的 k 个最强值 图解题解
这道题到底在问什么
- 输入
- arr=[1,2,3,4,5], k=2
- 输出
- [5,1]
- 输入
- arr=[1,1,3,5,5], k=2
- 输出
- [5,5]
- 输入
- arr=[6,7,11,7,6,8], k=5
- 输出
- [11,8,6,6,7]
最优解：一步一步想明白
- 3记牢一句:排好序后最强的躲在两端,左右指针每轮挑离中位数更远的那个,平局取右端更大的值。
- 4先看原始输入,arr = [4,1,7,2,6,5,3],一共 7 个数,要挑最强的 3 个。强弱要靠中位数来定,所以第一步得把数组排好序,才能找到中位数。
- 5把 arr 从小到大排好,变成 [1,2,3,4,5,6,7]。排序是这道题的地基:既为了取中位数,也为了用上「最远的躲在两端」这个性质。下面在这排有序的数上找中位数。
- 6中位数取排好序后下标 (7 减 1) 整除 2 也就是下标 3 处的数,值是 4。注意是按下标取正中间那个,不是求平均。这个 4 就是衡量强弱的基准点,谁离它越远谁越强。
- 7数 1 到中位数 4 的距离是 |1 减 4| = 3。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。
- 8数 2 到中位数 4 的距离是 |2 减 4| = 2。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。
- 9数 3 到中位数 4 的距离是 |3 减 4| = 1。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。
- 10数 4 到中位数 4 的距离是 |4 减 4| = 0。它正好就是中位数本身,距离 0,是最弱的,最后才会被考虑。
- 11数 5 到中位数 4 的距离是 |5 减 4| = 1。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。
- 12数 6 到中位数 4 的距离是 |6 减 4| = 2。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。
- 13数 7 到中位数 4 的距离是 |7 减 4| = 3。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。
- 14左指针 l 指向最左的 1,右指针 r 指向最右的 7。这两个数离中位数最远,最强的一定在它俩里产生。每一轮比一下谁更远,挑出更远的,指针往里收。开始挑第 1 个。
- 15看两端:左边 1 离中位数 3,右边 7 离中位数 3。距离打平,都是 3,这时比值的大小,谁大谁更强。右端 7 比左端 1 大,所以右端更强。
- 16把 7 挑出来标绿,放进结果,现在结果是 [7]。右指针往里收一格,新的右端是 6,接着比下一轮。
- 17看两端:左边 1 离中位数 3,右边 6 离中位数 2。左边离得更远,3 比 2 大,左端 1 更强。
- 18把 1 挑出来标绿,放进结果,现在结果是 [7,1]。左指针往里收一格,新的左端是 2,接着比下一轮。
- 19看两端:左边 2 离中位数 2,右边 6 离中位数 2。距离打平,都是 2,这时比值的大小,谁大谁更强。右端 6 比左端 2 大,所以右端更强。
- 20把 6 挑出来标绿,放进结果,现在结果是 [7,1,6]。右指针往里收一格,新的右端是 5,已经挑满 3 个,可以收工。
- 21挑满 3 个,结果是 [7,1,6]。回看这三个数:7 离中位数 4 的距离是 3,1 离 4 的距离是 3,6 离 4 的距离是 2,确实是离中位数最远的三个,跟开头说的对上了。题目允许任意顺序,所以 [7,1,6] 的任何排列都算对。
- 22换个角度印证一下。如果把 7 个数全按强弱从高到低排,会得到 [7,1,6,2,5,3,4]:先按到中位数的距离从大到小,距离一样再按值从大到小。这一排的前 3 个正好就是 [7,1,6]。双指针其实就是在不整排重排的前提下,只把这前 3 个高效地挑了出来。
- 23整道题串起来就三步:先排序,在有序数组上取下标 3 处的中位数 4;再认准最远的躲在两端;最后左右指针每轮挑离 4 更远的那个,平局取右端更大的值,挑满 3 个收工。答案 [7,1,6]。
⚠️ 容易写错的地方
✗ 错：把中位数当成「平均值」或「正中间两数的均值」
✓ 对：是排序后下标 (n 减 1) 整除 2 处的那个元素值
题目明确中位数取下标 (n 减 1) 整除 2。n 是偶数时取的是偏左那个,不是两数平均。取错基准 m,后面所有距离全错
✗ 错：距离相等时随便挑一个
✓ 对：距离相等必须取值更大的那个
规则第二条说得很清楚:|a 减 m| 等于 |b 减 m| 时,a > b 才算 a 更强。比如离中位数同样远的 1 和 7,要挑 7 不是 1。双指针里排序后右端值更大,所以平局取右端
✗ 错：Java 直接对 int 数组套自定义比较器
✓ 对：基本类型数组要先装箱进 List 才能用 Comparator
Java 的 Arrays.sort 对 int 数组只支持升序,不接受 Comparator。想按距离自定义排,必须把数装箱成 Integer 放进 List 再排,Python 和 C++ 没有这个限制
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def getStrongest(self, arr: List[int], k: int) -> List[int]:
arr.sort()
m = arr[(len(arr) - 1) >> 1]
arr.sort(key=lambda x: (-abs(x - m), -x))
return arr[:k]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> getStrongest(vector<int>& arr, int k) {
sort(arr.begin(), arr.end());
int m = arr[(arr.size() - 1) >> 1];
sort(arr.begin(), arr.end(), [&](int a, int b) {
int x = abs(a - m), y = abs(b - m);
return x == y ? a > b : x > y;
});
vector<int> ans(arr.begin(), arr.begin() + k);
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] getStrongest(int[] arr, int k) {
Arrays.sort(arr);
int m = arr[(arr.length - 1) >> 1];
List<Integer> nums = new ArrayList<>();
for (int v : arr) {
nums.add(v);
}
nums.sort((a, b) -> {
int x = Math.abs(a - m);
int y = Math.abs(b - m);
return x == y ? b - a : y - x;
});
int[] ans = new int[k];
for (int i = 0; i < k; ++i) {
ans[i] = nums.get(i);
}
return ans;
}
}复杂度
时间
O(n log n)
n 是数组长度。主导开销是排序:第一次升序排 O(n log n) 定中位数,第二次按强弱排还是 O(n log n);双指针挑 k 个或取前 k 个只是 O(k),被排序盖过。所以总体 O(n log n)
空间
O(log n) 到 O(n)
不算返回的结果列表(O(k))的话:C++ 原地排序约 O(log n) 递归栈;Python 的 list.sort 最坏 O(n);Java 额外建了一个装箱的 ArrayList,固定 O(n)。按峰值看,Java 与 Python 这一档是 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组中的 k 个最强值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么排序后只看两端就够,不用把整排按距离重排?+
因为数组升序排过以后,离中位数的距离是从两端向中间递减的:最左和最右的数离中位数最远,越往中间越近。所以任何时刻当前最强的数,只可能是还没选的区间的左端或右端,比一下这两个谁更远就能定。每选一个就把对应指针往里收,这样一轮一个、挑 k 个只花 O(k),省掉了对整排按距离重排的那次排序。
中位数为什么取下标 (n 减 1) 整除 2,偶数长度时是哪一个?+
题目把中位数定义成排序后正中间位置的元素,位置就是下标 (n 减 1) 整除 2。n 是奇数时这就是唯一的正中间;n 是偶数时,(n 减 1) 整除 2 会取到偏左的那个,比如长度 4 取下标 1。它要的是一个确定的元素值,不是中间两数的平均,所以照下标取就行,不用考虑平均。
这题和找第 k 大或者堆 Top K 有什么联系?+
本质都是按某个「强弱」标准取前 k 个。本题的强弱标准是到中位数的距离加上值的大小,先排序就能 O(n log n) 解决。如果只想要前 k 个而不在乎完整排序,也可以用一个大小为 k 的堆,或者用快速选择把前 k 个划出来,把复杂度压到接近 O(n)。面试里能点出「排序最直接,堆或快选可以进一步优化」就很完整了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组中的 k 个最强值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。