题目描述
思路解析动画文字版
记牢一句:排好序后最强的躲在两端,左右指针每轮挑离中位数更远的那个,平局取右端更大的值。
总览 · 原始输入：先看原始输入,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)。
参考代码
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]复杂度
- 时间：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)
易错点
面试追问把动画讲成自己的话
追问为什么排序后只看两端就够,不用把整排按距离重排?
追问中位数为什么取下标 (n 减 1) 整除 2,偶数长度时是哪一个?
追问这题和找第 k 大或者堆 Top K 有什么联系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
满足条件的子序列数目
LeetCode 1498 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题