数组中的 k 个最强值 图解题解

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

给你一个整数数组 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 处的那个元素值，不是平均数、也不是正中间两数的均值——偶数长度时取偏左那个，基准一错，后面每个距离都跟着错。平局那条也常被忽略：规则写死取值更大的，随手挑左边的小值就漏掉真正更强的数；有重复值别去重，照原样比就行。

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;
    }
}