[LeetCode] 462. Minimum Moves to Equal Array Elements II

轉自LeetCode

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.

<Solution>

這題是 453. Minimum Moves to Equal Array Elements 的衍生題

差別在於，這次可以加1也可以減1

假如有 a、b兩點，c 點在 a、b 中間的一個位置，能讓 a 到 c，以及 b 到 c 加起來的距離是最短

而 a 到 c 的距離加上 b 到 c 的距離，其實就是 a 到 b 的距離

因此，解題想法如下

• 先將 input 做 sort

• 兩個指標，一個指標從頭，一個指標從尾，因為 sort 過，所以兩點可視作一條線的兩端，相減即是所要找的距離

code 如下

C++

	class Solution {
	public:
	int minMoves2(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	int ans = 0;
	int start = 0, end = nums.size()-1;
	while(start < end) {
	ans += nums[end--] - nums[start++];
	}
	return ans;
	}
	};

view raw minMoveToEqualArray2.cpp hosted with ❤ by GitHub