[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