§1

题目描述

把规则抠清楚。先定中位数 m:把数组排好序,取下标 (n 减 1) 整除 2 处的那个数(n 是长度)。再比强弱:对两个数 a 和 b,如果 |a 减 m| > |b 减 m|,a 更强;如果 |a 减 m| 和 |b 减 m| 相等,就看值,a > b 时 a 更强。按这套从强到弱排,取前 k 个就是答案,顺序随意。本节盯着 arr = [4,1,7,2,6,5,3]、k = 3,看它挑出 [7,1,6]。

输入 = 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]

§2

思路解析

一句话答案：LeetCode 1471 数组中的 k 个最强值：排序后取下标（n−1）整除 2 的中位数，离它越远越强、平局取值大；排好序最强的必在两端，用对撞双指针从两头往里挑 k 个。时间 O(n log n)、空间 O(n)。

谁算「强」，这题要挑哪几个数

给你一个整数数组 arr 和一个数 k，要挑出最「强」的 k 个值返回，顺序随意。强弱这么定：先把 arr 排好序，取下标（n−1）整除 2 处的那个数当中位数 m（n 是长度）；一个数离 m 越远就越强，若两个数离 m 一样远，就比它们本身、值大的更强。拿题面第一个例子 arr=[1,2,3,4,5]、挑 2 个：中位数是正中间的 3，离 3 最远的是两头的 1 和 5，都差 2，平局取值大的先要 5，再要 1，答案 [5,1]。

整排重排取前 k，和对撞双指针同级

页面参考代码走一条直接的路：排序定出中位数后，给每个数算到中位数的距离，再用一次带 key 的整排重排，取前 k 个。这趟重排和先排序同级、都是 O(n log n)，并不浪费；这里讲的对撞双指针是等价写法，同样先排序，但不重排整排，只盯两端来挑，复杂度一样、更直观。

排好序后，最强的为什么必躲在两端

排好序后有个能省事的规律：离中位数的距离，从正中间往两边只增不减，中位数那格差 0，越靠边差得越大。于是还没挑走的那段里，最强的只可能是它的最左端或最右端。比一下两端谁离中位数远，远的就是当前最强，挑走它、把这端往里收一格，再看新的两端。这样不必把整排按强弱重排，从两头对着挑就够，这就是对撞双指针：左右两个指针从数组两头往中间收。

两端怎么比、指针往哪收、平局挑谁

左指针 l 从最左出发，右指针 r 从最右出发。每轮拿 arr[l] 和 arr[r] 到中位数 m 的距离比大小：若 |arr[l]−m| ＞ |arr[r]−m|，左端更强，挑走 arr[l]、l 往右挪一格；若反过来是＜，挑走 arr[r]、r 往左挪一格。距离一样时按值大的算强，升序数组里右端的值总不小于左端，所以平局固定取 arr[r]、r 左移。每挑一个计一次数，够 k 个就停。

arr=[4,1,7,2,6,5,3] 两头往里收挑 3 个

先升序排成 [1,2,3,4,5,6,7]，取下标 3 处的 4 当中位数。左指针指着 1、右指针指着 7：两头到 4 的距离 |1−4|=3、|7−4|=3，打平，取值大的 7，结果 [7]，右指针收到 6。再比：左端 1 差 3、右端 6 差 |6−4|=2，左边更远，挑 1，结果 [7,1]，左指针收到 2。又比：左端 2 差 |2−4|=2、右端 6 差 2，又打平，取更大的 6，结果 [7,1,6]，已经挑满 3 个，收工。答案 [7,1,6]。

中位数别读成平均，平局别顺手挑左边

整体复杂度被排序压着，是 O(n log n)，双指针挑 k 个只多花 O(k)、被排序盖过；空间上 C++ 原地排序约 O(log n)，Python 的排序最坏 O(n)，Java 因为要把 int 装箱进列表再排，固定 O(n)。

最容易栽的是中位数：它是排序后下标（n−1）整除 2 处的那个元素值，不是平均数、也不是正中间两数的均值——偶数长度时取偏左那个，基准一错，后面每个距离都跟着错。平局那条也常被忽略：规则写死取值更大的，随手挑左边的小值就漏掉真正更强的数；有重复值别去重，照原样比就行。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

记牢一句:排好序后最强的躲在两端,左右指针每轮挑离中位数更远的那个,平局取右端更大的值。

总览 · 原始输入：先看原始输入,arr = [4,1,7,2,6,5,3],一共 7 个数,要挑最强的 3 个。强弱要靠中位数来定,所以第一步得把数组排好序,才能找到中位数。

第 1 步 · 升序排序：把 arr 从小到大排好,变成 [1,2,3,4,5,6,7]。排序是这道题的地基:既为了取中位数,也为了用上「最远的躲在两端」这个性质。下面在这排有序的数上找中位数。

第 2 步 · 找中位数：中位数取排好序后下标 (7 减 1) 整除 2 也就是下标 3 处的数,值是 4。注意是按下标取正中间那个,不是求平均。这个 4 就是衡量强弱的基准点,谁离它越远谁越强。

量距离 · arr[0] = 1：数 1 到中位数 4 的距离是 |1 减 4| = 3。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。

量距离 · arr[1] = 2：数 2 到中位数 4 的距离是 |2 减 4| = 2。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。

量距离 · arr[2] = 3：数 3 到中位数 4 的距离是 |3 减 4| = 1。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。

量距离 · arr[3] = 4：数 4 到中位数 4 的距离是 |4 减 4| = 0。它正好就是中位数本身,距离 0,是最弱的,最后才会被考虑。

量距离 · arr[4] = 5：数 5 到中位数 4 的距离是 |5 减 4| = 1。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。

量距离 · arr[5] = 6：数 6 到中位数 4 的距离是 |6 减 4| = 2。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。

量距离 · arr[6] = 7：数 7 到中位数 4 的距离是 |7 减 4| = 3。把它记在右边面板里。你会发现越靠两端的数距离越大,这正是下一步只盯两端的底气。

第 3 步 · 两端放指针：左指针 l 指向最左的 1,右指针 r 指向最右的 7。这两个数离中位数最远,最强的一定在它俩里产生。每一轮比一下谁更远,挑出更远的,指针往里收。开始挑第 1 个。

第 1 轮 · 比两端距离：看两端:左边 1 离中位数 3,右边 7 离中位数 3。距离打平,都是 3,这时比值的大小,谁大谁更强。右端 7 比左端 1 大,所以右端更强。

第 1 轮 · 选 7：把 7 挑出来标绿,放进结果,现在结果是 [7]。右指针往里收一格,新的右端是 6,接着比下一轮。

第 2 轮 · 比两端距离：看两端:左边 1 离中位数 3,右边 6 离中位数 2。左边离得更远,3 比 2 大,左端 1 更强。

第 2 轮 · 选 1：把 1 挑出来标绿,放进结果,现在结果是 [7,1]。左指针往里收一格,新的左端是 2,接着比下一轮。

第 3 轮 · 比两端距离：看两端:左边 2 离中位数 2,右边 6 离中位数 2。距离打平,都是 2,这时比值的大小,谁大谁更强。右端 6 比左端 2 大,所以右端更强。

第 3 轮 · 选 6：把 6 挑出来标绿,放进结果,现在结果是 [7,1,6]。右指针往里收一格,新的右端是 5,已经挑满 3 个,可以收工。

完成 · 最强 3 个：挑满 3 个,结果是 [7,1,6]。回看这三个数:7 离中位数 4 的距离是 3,1 离 4 的距离是 3,6 离 4 的距离是 2,确实是离中位数最远的三个,跟开头说的对上了。题目允许任意顺序,所以 [7,1,6] 的任何排列都算对。

印证 · 全量按强弱排：换个角度印证一下。如果把 7 个数全按强弱从高到低排,会得到 [7,1,6,2,5,3,4]:先按到中位数的距离从大到小,距离一样再按值从大到小。这一排的前 3 个正好就是 [7,1,6]。双指针其实就是在不整排重排的前提下,只把这前 3 个高效地挑了出来。

回放 · 一句话套路：整道题串起来就三步:先排序,在有序数组上取下标 3 处的中位数 4;再认准最远的躲在两端;最后左右指针每轮挑离 4 更远的那个,平局取右端更大的值,挑满 3 个收工。答案 [7,1,6]。

边界:平局取更大的值;有重复值不去重照样比;只取 1 个时在最远的一对里挑值大的那个。

面试重点:排序后最远的在两端故只看两端;中位数取下标 (n 减 1) 整除 2 的元素;先定中位数后,堆可做到 O(n log k)、快选平均 O(n),若仍完整排序求中位数则总体 O(n log n)。

§3

参考代码

from __future__ import annotationsfrom 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]

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间：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)

§5

易错点

✗ 错误写法：把中位数当成「平均值」或「正中间两数的均值」

✓ 正确写法：是排序后下标 (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++ 没有这个限制

面试追问把动画讲成自己的话

追问为什么排序后只看两端就够,不用把整排按距离重排?

因为数组升序排过以后,离中位数的距离是从两端向中间递减的:最左和最右的数离中位数最远,越往中间越近。所以任何时刻当前最强的数,只可能是还没选的区间的左端或右端,比一下这两个谁更远就能定。每选一个就把对应指针往里收,这样一轮一个、挑 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)。面试里能点出「排序最直接,堆或快选可以进一步优化」就很完整了。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 双指针套路 37/48

满足条件的子序列数目

LeetCode 1498 · 中等 · 沿着双指针套路继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

899道动画图解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

from __future__ import annotationsfrom 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]