462. 最小操作次数使数组元素相等 II——【Leetcode每日一题】

462. 最小操作次数使数组元素相等 II

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

示例 1：

输入：nums = [1,2,3]
输出：2
解释：
只需要两次操作（每次操作指南使一个元素加 1 或减 1）：
[1,2,3] => [2,2,3] => [2,2,2]

示例 2：

输入：nums = [1,10,2,9]
输出：16

提示：

• $n==nums.length$
• $1<=nums.length<=10^5$
• $-10^9<=nums[i]<=10^9$

思路：

每次可以对一个数组元素加一或者减一，求最小的改变次数。

这是个典型的相遇问题，移动距离最小的方式是所有元素都移动到中位数。理由如下：

• 设 m 为中位数。a 和 b 是 m 两边的两个元素，且 b > a。
• 要使 a 和 b 相等，它们总共移动的次数为 b - a，这个值等于 (b - m) + (m - a)，
• 也就是把这两个数移动到中位数的移动次数。

设数组长度为 N，则可以找到 N/2 对 a 和 b 的组合，使它们都移动到 m 的位置。

代码：(Java、C++)

Java

import java.util.Arrays;

public class MinMoves2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] nums = {1, 10, 2, 9};
		System.out.println(minMoves2(nums));
	}
	public static int minMoves2(int[] nums) {
		Arrays.sort(nums);
		int l = 0, h = nums.length - 1;
		int moves = 0;
		while(l < h) {
			moves += nums[h--] - nums[l++];
		}
		return moves;
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int main() {

	MinMoves2 m;
	vector<int> nums = {1,10,2,9 };

	cout << m.minMoves2(nums) << endl;

	system("pause");
	return 0;
}

运行结果：

复杂度分析：

• 时间复杂度：$O(nlogn)$，其中 n 是数组 nums 的长度。排序需要 $O(nlogn)$的时间。
• 空间复杂度：$O(logn)$。排序需要 $O(logn)$的递归栈空间。

题目来源：力扣。

注：仅供学习参考， 如有不足，欢迎指正！