Created time
May 25, 2022 02:37 PM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug
最少移动次数使数组元素相等 II
给你一个长度为
n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。相关标签：数组, 数学, 排序。Minimum Moves to Equal Array Elements II
Given an integer array
nums of size n, return the minimum number of moves required to make all array elements equal. In one move, you can increment or decrement an element of the array by 1. Test cases are designed so that the answer will fit in a 32-bit integer. Related Topics: Array, Math, Sorting.这个题是给我们一个非空数组，然后我们每一次可以将其中一个元素加一或者减一，然后目标是使所有元素相等，问我们最少进行多少次操作。
这个题首先我们第一点先想一下这个答案最终变成的元素是不是一定是数组里面的元素？有这样一个结论就是一定存在最优解，注意啊不一定所有最优解都是变成数组里面的元素但是一定存在最优解。假设存在一个最优解，使得什么呢？使得最终数组变成的数一定是数组里面没有的元素。数组里面最终变成的数一定是数组里面的没有元素，这个其实比较容易证明，假设在一个平面直角坐标中我们最终的的元素是一条虚线，假设所有点都不在虚线上，就是你假设这个最优解不是取得数组里面的已有的值的话，那我们可以统计一下，假设上面有x个点，下面有y个点，那你可以看一下x和y的关系：
- 如果x<y的话，就是y比较多的话，那么我们将虚线往下移动一单位的距离，那么上面x个点距离这条虚线的距离就一共增加了x，下面的y个点的距离就整体减少了一个y。那y就小于零了，那么我们将线向下移动一格，答案就会变小，就矛盾了。
- 反过来如果x>y的话，那么我们将整个线往上移动一格，它的答案也会变小，也矛盾了是吧。
- 那么如果x=y的话，那么我们不管将线向上移还是向下移一单位。它这个总和是不变的，就是一共向上移一单位的话，那么上面的所有元素的距离和是减了x，下面是加了y，然后xy相等就是零。所以xy相等的话你可以将这条线一直往上移，直到移到某个点为止，所以必然存在一个最优解使得数组最终变成的元素一定是数组里面没有的元素，那因此我们在枚举答案的时候，只需要枚举数组里面有的元素就可以了。
然后我们为了方便，就是大家可以发现这个题的答案跟数组里面的数据是无所谓的是吧。所以为了方便的话我们可以把数组排个序，从小到大排个序。然后每次枚举一下最终数组里面变成哪个数。假设当前数组里面变成这个数，我们去枚举数组里面所有元素变成这个数，那就意味所有小于这个数的元素都要变成这个数，所有大于这个数的也都要变成这个数。那么所有小于这个数你都要通过加一来变成这个数，那么一共加多少呢？这是可以直接算的，就是我们假设这个数是x，第i个数。那么一共加多少呢？那就是等价于。这是左边需要加的值，那么右边需要加的值呢？右边所有值都比x要大对吧，都大于等于x。所以右边就是整理一下就是，这是右边需要加的值。那么大家可以发现我们枚举完x之后公式的前面两项可以直接算，因为就是一个乘法，后面的话就是一个预处理的前缀和。这样的话就可以很快的算出两部分的和。这个是第一种做法，这个做法只需要排个序预处理前缀和就可以做了。