1551. 使数组中所有元素相等的最小操作数

• 标签：数学
• 难度：中等

题目链接

• 1551. 使数组中所有元素相等的最小操作数 - 力扣

题目大意

描述：存在一个长度为 $n$ 的数组 $arr$，其中 $arr[i] = (2 \times i) + 1$，$(0 \le i < n)$。

在一次操作中，我们可以选出两个下标，记作 $x$ 和 $y$（$0 \le x, y < n$），并使 $arr[x]$ 减去 $1$，$arr[y]$ 加上 $1$）。最终目标是使数组中所有元素都相等。

现在给定一个整数 $n$，即数组 $arr$ 的长度。

要求：返回使数组 $arr$ 中所有元素相等所需要的最小操作数。

说明：

• 题目测试用例将会保证：在执行若干步操作后，数组中的所有元素最终可以全部相等。
• $1 \le n \le 10^4$。

示例：

• 示例 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：贪心

通过观察可以发现，数组中所有元素构成了一个等差数列，为了使所有元素相等，在每一次操作中，尽可能让较小值增大，让较大值减小，直到到达平均值为止，这样才能得到最小操作次数。

在一次操作中，我们可以同时让第 $i$ 个元素增大与第 $n - 1 - i$ 个元素减小。这样，我们只需要统计出数组前半部分元素变化幅度即可。

思路 1：代码

class Solution:
    def minOperations(self, n: int) -> int:
        ans = 0
        for i in range(n // 2):
            ans += n - 1 - 2 * i
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

思路 2：贪心 + 优化

数组前半部分元素变化幅度的计算可以看做是一个等差数列求和，所以我们可以直接根据高斯求和公式求出结果。

$\lbrace n - 1 + [n - 1 - 2 * (n \div 2 - 1)]\rbrace \times (n \div 2) \div 2 = n \times n \div 4$

思路 2：代码

class Solution:
    def minOperations(self, n: int) -> int:
        return n * n // 4

思路 2：复杂度分析

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。