這道題一直在思考O(n)解法浪費(fèi)了很多時(shí)間泥彤，應(yīng)當(dāng)保證能做出的情況下去思考比較好。卿啡。吟吝。自己寫(xiě)的效率還行。
我的解法
class Solution {
public:
int minMoves2(vector<int>& nums) {
int output = 0;
sort(nums.begin(), nums.end());
int middle = nums[nums.size()/2];
for (int i = 0; i < nums.size(); i ++)
output += abs(nums[i] - middle);
return output;
}
};
別人的解法
- 別人的解法1
這里這個(gè)nth_element時(shí)間復(fù)雜度只有O(n)颈娜，很厲害的樣子剑逃。
// O(n).
// Imagine the nums are sorted, and the final value is k, we start find k from the first element.
// If we increase k, the elements <= k will need move one step more, and the elements > k will need to move one step less.
// If there are more elements > k than elements <= k, we should increase k to minimize the moves.
// So we just increase k, until k reach the median of of the nums array. By then, the number of elements <= k equals to that of elements > k.
// (There is a slight different when the number of array is odd, but it's similar).
// If we keep increasing k after k reach the median of the array, more numbers >k than <= k, and more moves needed, so we should stop.
//
// The sort is not needed since we find the k is the median of the array, there is an average O(n) algorithm to find such k.
class Solution {
public:
int minMoves2(vector<int>& nums) {
int n = nums.size();
auto it = nums.begin() + n/2;
nth_element(nums.begin(), it, nums.end());
int median = *it;
int total = 0;
for (auto &i : nums)
total += abs(i-median);
return total;
}
};
- 別人的解法2
思考結(jié)果本質(zhì)上是一樣的，但是思維的過(guò)程不太一樣官辽，可以想一想蛹磺。
int minMoves2(vector<int>& nums) {
sort(nums.begin(), nums.end()); int n = nums.size(), res = 0;
for (int i = 0; i < n/2; ++i) res += (nums[n-1-i]-nums[i]);
return res;
}
