1471. The k Strongest Values in an Array

题目信息

题号:

1471

难度:

Medium

主题:

数组、排序、双指针

原题:

LeetCode 1471

重点:

中位数为排序后下标 (n-1)/2 的元素;离中位数更远者更强,距离并列时数值更大者更强

题目重述

给定整数数组 arr 和整数 k。先将数组排序,定义中位数 m = arr[(n-1)/2]。

若 |a-m| > |b-m|,或两者距离相等且 a > b,则 a 比 b 更强。请返回数组中最强的 k 个元素,返回顺序不限,重复元素按实例计数。

1 <= arr.length <= 10^5,-10^5 <= arr[i] <= 10^5,1 <= k <= arr.length。

自建示例

距离并列时选择数值较大的元素:

输入:arr = [1,2,3,4,5], k = 2
输出:[5,1]
解释:中位数为 3,1 和 5 距离均为 2,5 的强度更高,但二者都是最强的两个元素。

只含一个元素时直接返回该元素:

输入:arr = [-4], k = 1
输出:[-4]
解释:数组中只有一个候选元素。