数组元素均等化最小操作数优化：修复现有解法的效率与逻辑问题

问题规则 #

给定一个数字数组，需找出使所有元素相等所需的最小操作次数，操作规则如下：

• 操作按顺序从1到m编号
• 奇数编号操作：可选择数组中一个元素加1
• 偶数编号操作：可选择数组中一个元素加2，也可选择不执行操作（最优策略下不会选择不执行，除非必须）

示例 #

数组A = [1,2,4]，操作过程如下：

operation 1, odd, select 1st item add 1 , A= [2,2,4]
operation 2, even, select 1st item add 2, A = [4,2,4]
operation 3, odd, do nothing
operation 4, even, select 2nd item add 2, A = [4,4,4]

最终结果为4。

原解法代码及问题 #

原代码 #

public long solve(int[] arr) {
    int max = Arrays.max(arr);
    List<Integer> list = new ArrayList<>();
    for(int e : arr) {
        if(max - e >0) list.add(max - e);
    }

    Collections.sort(list);
    int n = list.size();
    long result = 0;
    for(int i=0, j=n-1, k=1; i <=j; k++) {
        if(k%2==1) {// odd
            int e = list.get(i);
            e--;
            list.set(i, e);
            if(e <=0) i++;
        } else {// even
            int e = list.get(j);
            e -= 2;
            list.set(j, e);
            if(e <=0) j--;
        }
       result++;
    }
}

存在的问题 #

1. 时间效率低下：通过逐次模拟操作计数，当数组元素与最大值的差值较大时，循环次数会呈线性增长，导致运行时间过长，时间复杂度为O(sum(d_i))，其中d_i是元素与最大值的差值。
2. 逻辑缺陷：假设排序后的差值列表始终保持头部小、尾部大的状态，固定用头部元素处理奇数操作、尾部元素处理偶数操作，但迭代中尾部元素可能被减至小于头部元素，此时继续按原逻辑处理会导致操作次数非最优，甚至逻辑错误。

高效解决方案 #

思路分析 #

要让所有元素等于数组最大值max，我们只需关注每个元素与max的差值d_i = max - arr[i]（仅考虑d_i > 0的情况）：

1. 设sum_d为所有正差值的总和，total_a为差值中奇数的数量（每个奇数差值至少需要1次奇数操作来覆盖奇偶性）。
2. 操作是奇偶交替的，总操作次数m对应的奇数操作次数x = (m+1)//2，偶数操作次数y = m//2。
3. 需满足两个核心约束：
   • 奇数操作次数x必须≥total_a（覆盖所有奇数差值的奇偶性需求）
   • 总增量x + 2*y必须≥sum_d（覆盖所有差值的总和）

我们可以通过二分查找快速找到满足这两个约束的最小m，避免逐次模拟的低效。

实现代码 #

import java.util.Arrays;

public long solve(int[] arr) {
    if (arr == null || arr.length == 0) return 0;
    int max = Arrays.stream(arr).max().getAsInt();
    long sumD = 0;
    int totalA = 0;
    for (int num : arr) {
        int d = max - num;
        if (d > 0) {
            sumD += d;
            if (d % 2 != 0) {
                totalA++;
            }
        }
    }
    if (sumD == 0) return 0;
    // 二分查找最小操作次数
    long left = Math.max(totalA, (sumD + 1) / 2);
    long right = sumD; // 最坏情况：全用奇数操作
    long answer = right;
    while (left <= right) {
        long mid = left + (right - left) / 2;
        long oddOps = (mid + 1) / 2;
        long evenOps = mid / 2;
        // 检查是否满足两个约束
        if (oddOps >= totalA && oddOps + 2 * evenOps >= sumD) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
}

代码说明 #

1. 首先计算数组最大值，然后遍历数组得到差值总和sumD和奇数差值的数量totalA。
2. 二分查找的左边界设为max(totalA, (sumD+1)/2)：前者保证满足奇数操作的最小需求，后者是理论上的最小操作次数（每次操作最多贡献2）。
3. 右边界设为sumD（最坏情况，所有操作都用奇数操作）。
4. 每次二分迭代中，计算当前mid对应的奇偶操作次数，验证是否满足约束，逐步缩小范围找到最小m。

内容的提问来源于stack exchange，提问作者Learner