Given an array of integers arr
and an integer k
.
A value arr[i]
is said to be stronger than a value arr[j]
if |arr[i] - m| > |arr[j] - m|
where m
is the median of the array.
If |arr[i] - m| == |arr[j] - m|
, then arr[i]
is said to be stronger than arr[j]
if arr[i] > arr[j]
.
Return a list of the strongest k
values in the array. return the answer in any arbitrary order.
Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2)
in the sorted list (0-indexed).
- For
arr = [6, -3, 7, 2, 11]
,n = 5
and the median is obtained by sorting the arrayarr = [-3, 2, 6, 7, 11]
and the median isarr[m]
wherem = ((5 - 1) / 2) = 2
. The median is6
. - For
arr = [-7, 22, 17, 3]
,n = 4
and the median is obtained by sorting the arrayarr = [-7, 3, 17, 22]
and the median isarr[m]
wherem = ((4 - 1) / 2) = 1
. The median is3
.
Example 1:
Input: arr = [1,2,3,4,5], k = 2 Output: [5,1] Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer. Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.
Example 2:
Input: arr = [1,1,3,5,5], k = 2 Output: [5,5] Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].
Example 3:
Input: arr = [6,7,11,7,6,8], k = 5 Output: [11,8,6,6,7] Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7]. Any permutation of [11,8,6,6,7] is accepted.
Example 4:
Input: arr = [6,-3,7,2,11], k = 3 Output: [-3,11,2]
Example 5:
Input: arr = [-7,22,17,3], k = 2 Output: [22,17]
Constraints:
1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length
Solution 1: quick selection + sort
Step 1: find the median element m
Step 2: Sort the array according to m
Step 3: output the first k elements of the sorted array.
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: vector<int> getStrongest(vector<int>& arr, int k) { const int n = arr.size(); const int i = (n - 1) / 2; // sort(begin(arr), end(arr)); nth_element(begin(arr), begin(arr) + i, end(arr)); const int m = arr[i]; sort(begin(arr), end(arr), [&](const int x, const int y) { return abs(x - m) != abs(y - m) ? abs(x - m) > abs(y - m) : x > y; }); return {begin(arr), begin(arr) + k}; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment