## [1471\. 數組中的 k 個最強值](https://leetcode-cn.com/problems/the-k-strongest-values-in-an-array/) #### 思路 說下我的思路 * 先算出中位數 * 遍歷數組，算出每個數和中位數的差值，保存 * 同時保存下標，應為當差值相同是，下標也要作為權重的判斷依據 * 將數組按規則進行排序 * 返回前k個值 AC！ #### 代碼 python ``` class Solution: def getStrongest(self, arr, k): s = sorted(arr) mindex = (len(s) - 1) // 2 mvalue = s[mindex] temp = [] for i in s: temp.append([abs(i-mvalue),i]) def sorttemp(s1,s2): if s1[0] < s2[0]: return 1 if s1[0] > s2[0]: return -1 if s1[0] == s2[0] and s1[1] > s2[1]: return -1 return 1 return [x[1] for x in sorted(temp, sorttemp)[:k]] ``` #### 代碼（大佬精簡版） python ``` class Solution: def getStrongest(self, arr: List[int], k: int) -> List[int]: n = len(arr) arr = sorted(arr) mid = arr[(n - 1) // 2] def mykey(x): return (abs(x - mid), x) arr = sorted(arr, key=mykey) return arr[n - k:] ``` **改進思路** 使用**排序+雙指針** * 先將數組排序，算出中位數 * 兩個指針分別指向排好序的數組的兩端 * 應為和中位數的差值最大，也就是距離最遠，肯定是越靠近兩端的約大 * 比較兩個指針的值和下標，分別向中間靠近，得到前k個值，即結果 周賽時考慮上面一種方法寫起來較快，而且沒有TLE。雙指針方法，沒有嘗試，代碼暫略。感興趣的小伙伴可以嘗試一下。