原文链接: https://leetcode-cn.com/problems/minimum-operations-to-make-array-equal
英文原文
You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e., 0 <= i < n).
In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e., perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.
Given an integer n, the length of the array, return the minimum number of operations needed to make all the elements of arr equal.
Example 1:
Input: n = 3 Output: 2 Explanation: arr = [1, 3, 5] First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4] In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].
Example 2:
Input: n = 6 Output: 9
Constraints:
1 <= n <= 104
中文题目
存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。
一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都 相等 。题目测试用例将会 保证 ：在执行若干步操作后，数组中的所有元素最终可以全部相等。
给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。
示例 1：
输入：n = 3 输出：2 解释：arr = [1, 3, 5] 第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4] 第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]
示例 2：
输入：n = 6 输出：9
提示：
1 <= n <= 10^4
通过代码
高赞题解
拿到这道题,感觉有点绕,仔细分析发现arr[i] = (2 * i) + 1 (0 <= i < n)是典型的等差数列(1,3,5,7,9…).
根据等差数列的求和公式,很容易求出数组arr的元素总和是n^2.
题设中说每次操作选出两个下标x y使arr[x]减一arr[y]加一.换句话说,无论怎样选择x y,无论操作多少次,数组的总和不会变.
题设又保证数组中所有元素最终可以全部相等.
那我们假设最终所有元素等于a那么n*a == n^2,所以a == n,也就是说最终数组元素都是n.其实n是数组的平均值.知道最终元素都是n后,通过从数组起始和末尾下标开始向中间遍历,就可以到达操作数最小.
假设左边的下标是i ((2 * i) + 1 < n)那么相应右边的下标是n - i.相应两个元素值与n的差都是n - 1 + 2 * i.所以我们只要计算数组中值小于n的元素与n的差的总和,就得到最小操作数了.
代码实现
int minOperations(int n) {
int operation = 0;
for(int i = 1; i < n ; i += 2) {
operation += (n - i);
}
return operation;
}
// 时间复杂度是O(n) 空间复杂度是O(1)因为是等差数列,很可能找到一个数学公式,用O(1)的时间复杂度解决.
先举几个简单的例子找找规律
- n=3 最小操作数是 2
- n=4 最小操作数是 1 + 3
- n=5 最小操作数是 2 + 4
- n=6 最小操作数是 1 + 3 + 5
- n=7 最小操作数是 2 + 4 + 6
果然有规律:
当n是偶数的时候,最小操作数是1 + 3 + 5 + ... + n-1 = n*n/4
当n是奇数的时候,最小操作数是2 + 4 + ... + n-1 = (n*n - 1) / 4
注意: 上面的求和公式都是数学形式
那能不能再简单一点呢? 如果用整除代替数学中的除法,可以将(n*n - 1) / 4修改成n*n/4,因为1整除4为0不影响最后的结果.
所以有了下面的代码,是不是很酷 :)
代码
int minOperations(int n) {
reutrn n * n / 4;
}
// 时空复杂度都是 O(1)觉得文章不错的话,点个赞呗~
如果发现文章有问题,烦请留言交流,谢谢大家.
全文完
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 11574 | 14162 | 81.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
