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

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

难度中等17收藏分享切换为英文接收动态反馈

存在一个长度为 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$ 的数字是$1、3、5、7、9、11、13、15$

• 如果 $n$ 是奇数，所有的数字都变成中间的数字即 $i=n/2$ 的那个数字
• 如果 $n$ 是偶数，中间的两个数字的 $index$ 是 $n-1/2$和$n-1/2+1$

结果是中间的那个值 $mid$ 减去它前面的每个数字$nums[i]$得到的结果的和

class Solution {
    public int minOperations(int n) {
        int res = 0;
        if (n % 2 == 0) {
            // n是偶数
            int val1 = 2 * ((n - 1) / 2) + 1;
            int val2 = 2 * ((n - 1) / 2 + 1) + 1;
            // 中间的那个数字的值
            int mid = (val1 + val2) / 2;
            for (int i = 0; i <= (n - 1) / 2; i++) {
                res += mid - (2 * i + 1);
            }
        } else {
            // n是奇数

            // 中间的那个数字的值
            int mid = 2 * (n / 2) + 1;

            for (int i = 0; i < n / 2; i++) {
                res += mid - (2 * i + 1);
            }
        }
        return res;
    }
}

贪心

只计算大于n的那一半的值

当$arr[i] = (2 * i) + 1 > n$时 $i=(n-1)/2$也就是中间的 $index$,与上述思路基本一致

class Solution {
    public int minOperations(int n) {
        int ret = 0, avg = n;
        for (int i = 0; i < n; i++) {
            int x = 2 * i + 1;
            if (x > n) {
                ret += x - n;
            }
        }
        return ret;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-operations-to-make-array-equal/solution/shi-shu-zu-zhong-suo-you-yuan-su-xiang-deng-de-z-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

数学

当$n$为奇数时
$\begin{aligned}
A N S &=\sum_{i=\frac{n-1}{2}}^{n-1}(2 \times i+1-n) \
&=(1-n) \times\left(n-1-\frac{n-1}{2}+1\right)+2 \times \sum_{i=\frac{n-1}{2}}^{n-1} i \
&=\frac{(1-n) \times(n+1)}{2}+2 \times \frac{(n+1) \times(3 \times n-3)}{8} \
&=\frac{n^{2}-1}{4}
\end{aligned}$

---

当$n$为偶数时
$\begin{aligned}
A N S &=\sum_{i=\frac{1}{2}}^{n-1}(2 \times i+1-n) \
&=(1-n) \times\left(n-1-\frac{n}{2}+1\right)+2 \times \sum_{i=\frac{n}{2}}^{n-1} \
&=\frac{(1-n) \times n}{2}+2 \times \frac{n \times(3 \times n-2)}{8} \
&=\frac{n^{2}}{4}
\end{aligned}$

注意到 $\frac{n^2 - 1}{4}=\lfloor \frac{n^2}{4}\rfloor$
我们可以直接用整除来算出结果。

class Solution {
    public int minOperations(int n) {
        return n * n / 4;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-operations-to-make-array-equal/solution/shi-shu-zu-zhong-suo-you-yuan-su-xiang-deng-de-z-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信