Medium
题目描述
给你一个长度为 n 的数组 arr，其中 arr[i] = (2 * i) + 1，对于所有有效的 i（即 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，使 arr 变为 [2, 3, 4]
第二次操作选择 x = 2 和 y = 0，使 arr 变为 [3, 3, 3]
示例 2：
输入：n = 6
输出：9
提示：
- 1 <= n <= 10^4
- 使用给定公式构建数组 arr，定义 target = sum(arr) / n
- 将 arr 转换为所有元素都等于 target 需要多少次操作？
解题思路
这道题可以通过数学方法巧妙解决，不需要真的构建数组。
首先分析数组的性质：
- arr[i] = 2*i + 1，所以数组为 [1, 3, 5, 7, …]
- 这是一个首项为1，公差为2的等差数列
- 数组总和为 n²，平均值（目标值）为 n
关键观察是：每次操作本质上是把较大的数向较小的数转移1个单位，为了使所有元素都等于平均值n，我们需要计算每个元素与目标值的差距。
有两种解法思路：
解法1：直接计算差距 对于前一半的元素（小于目标值），它们需要从后一半获得一定数量。操作数就是前一半元素与目标值差距的总和。
解法2：数学公式 通过数学推导可以发现：
- 当n为偶数时，答案为 n²/4
- 当n为奇数时，答案为 (n²-1)/4
这是因为数组的对称性，前一半需要的总量等于后一半多出的总量。
推荐使用数学公式解法，时间复杂度最优。
代码实现
class Solution {
public:
int minOperations(int n) {
return n * n / 4;
}
};
class Solution:
def minOperations(self, n: int) -> int:
return n * n // 4
public class Solution {
public int MinOperations(int n) {
return n * n / 4;
}
}
var minOperations = function(n) {
return Math.floor(n * n / 4);
};
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(1) |
| 空间复杂度 | O(1) |