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

青旅半醒 2024-03-24 12:52 49阅读 0赞

### 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 = = n u m s . l e n g t h n == nums.length n==nums.length
 *   1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
 *   − 1 0 9 < = n u m s \[ i \] < = 1 0 9 - 10^9 <= nums\[i\] <= 10^9 −109<=nums\[i\]<=109

#### 思路： ####

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

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

*  设 `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;
    }

##### 运行结果： #####

![在这里插入图片描述][b01783972f5a43aa8bdf212cc11dfc9a.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n l o g n ) O(nlogn) O(nlogn)，其中 `n` 是数组 `nums` 的长度。排序需要  O ( n l o g ⁡ n ) O(nlog⁡n) O(nlog⁡n)的时间。
 *  **空间复杂度**： O ( l o g n ) O(logn) O(logn)。排序需要  O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)的递归栈空间。

题目来源：[力扣。][Link 1]

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

[b01783972f5a43aa8bdf212cc11dfc9a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/1512651d9e2d438d82fc3d35cd47fadf.png
[Link 1]: https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/description/?orderBy=most_votes