LeetCode Minimum Moves to Equal Array Elements II Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1. You may assume the array’s length is at most 10,000. Example:
Input: [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]
是LeetCode Minimum Moves to Equal Array Elements的改编题。这次每次只能改变一个数，让其增大1或者减小1，问最小需要多少次操作能使所有数字相等。 其实看样例就能猜到，最终统一的那个数是原数组中的中位数。这就好办了，对原数组排个序，然后累加所有元素和中位数的绝对值就可以了。 代码如下： [cpp] class Solution { public: int minMoves2(vector<int>& nums) { sort(nums.begin(), nums.end()); int ans = 0, mid = nums[nums.size() / 2]; for (const int& i : nums)ans += abs(i – mid); return ans; } }; [/cpp] 本代码提交AC，用时22MS。 排好序之后还有另一种方法求操作数，比如排好序是1,3,5,7,9，最终所有数都要变成5。之前的做法是所有数和5作差求绝对值加和，现在可以这样做，1到5需要(5-1)次操作，9变成5需要(9-5)次操作，累加就是(5-1)+(9-5)=(9-1)，所以我们取排序之后的首位元素，互相作差即可。这就看起来和中位数没关系了。 代码如下： [cpp] class Solution { public: int minMoves2(vector<int>& nums) { sort(nums.begin(), nums.end()); int ans = 0, i = 0, j = nums.size() – 1; while (i < j) { ans += nums[j–] – nums[i++]; } return ans; } }; [/cpp] 本代码提交AC，用时19MS。 既然是要求中位数，其实不用对数组排序都可以做到，就是之前的求第k大数LeetCode Kth Largest Element in an Array，直接借用那个函数即可。STL也有类似的函数nth_element。 [cpp] class Solution { private: int helper(vector<int>& nums, int left, int right, int k) { if (left == right)return nums[left]; int pivot = nums[left]; int l = left, r = right; while (l < r) { while (l < r&&nums[r] <= pivot)–r; if (l >= r)break; nums[l] = nums[r]; while (l < r&&nums[l] >= pivot)++l; if (l >= r)break; nums[r] = nums[l]; } nums[l] = pivot; if (l + 1 == k)return pivot; if (k < l + 1)return helper(nums, left, l – 1, k); else return helper(nums, l + 1, right, k); } public: int minMoves2(vector<int>& nums) { //int ans = 0, mid = helper(nums, 0, nums.size() – 1, nums.size() / 2 + 1); nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end()); int ans = 0, mid = nums[nums.size() / 2]; for (const int& i : nums)ans += abs(i – mid); return ans; } }; [/cpp] 本代码提交AC，用时13MS。]]>