這題蠻玄的, 起初我就想要找平均數, 靠近平均數總和的那個數就行
殊不知這題在找的竟然是, 中位數
為什麼？
有個人給出簡單的證明
如果今天要找[1,2,3, 10]
對於中間找到的這個數無論是多少
對於1, 跟 10 要走的距離是一樣的
舉例
mid = x
abs(x - 1) + abs(10 - x)
x對於10跟1是一樣的所以問題可以再被我們收斂從n → n -2
這樣相當於就是在找中位數是多少, 只有他有影響
假設中位數是五
我們挑5, 相當於就是最後只有中位數在做選擇,class Solution {
public:
int minMoves2(vector<int>& nums) {
sort(nums.begin(), nums.end());
int idx = nums.size() / 2;
int mid = (nums[nums.size() / 2] + nums[(nums.size() - 1) / 2]) / 2;
int res = 0;
for(auto e: nums){
res += abs(e - mid);
}
return res;
}
};
上面時間用到O(n logn )
