[leetcode] 1471. The k Strongest Values in an Array

Description

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 array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
• For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

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

分析

题目的意思是：给你一个数组，按照要求给出K个强数，看完题目发现原来是离中位数越远越强，想到这个就好办了，首先排序找到中位数，然后利用两个指针由左向右进行遍历，计算遍历的数与中位数的绝对差值，谁大选谁。

代码

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        n=len(arr)
        i=0
        j=n-1
        arr.sort()
        m=arr[(n-1)//2]
        cnt=0
        res=[]
        while(i<=j and cnt!=k):
            left=abs(arr[i]-m)
            right=abs(arr[j]-m)
            if(right>=left):
                res.append(arr[j])
                j-=1
            else:
                res.append(arr[i])
                i+=1
            cnt+=1
        return res