求使数组所有元素相等的最小世代数：正确算法探究

问题描述 #

给定整数数组（如[1,1,2,4]），需通过重复操作让所有元素相等，规则如下：

• 初始状态为世代0（偶数世代）
• 奇数世代：可选择给某一个元素加1，或跳过操作进入下一世代
• 偶数世代：可选择给某一个元素加2，或跳过操作进入下一世代
  目标是返回达成所有元素相等状态所需的最少世代数。

示例：输入[1,1,2,4]预期输出为6；输入[2,2,4]时，现有算法输出4，但实际仅需3个世代即可完成。

失效代码分析 #

以下是LeetCode用户提供的失效JS代码：

// * g: [1, 2, 2, 4]
const ans = (arr) => {
    const eachCycleVal = 1 + 2; /*cycle contains decreasing 1 followed by 2*/
    const maxVal = Math.max(...arr);
    let totalCycles = 0;
    for (let i = 0; i < arr.length; i++) {
        arr[i] = maxVal - arr[i];
        arr[i] = Math.ceil(arr[i] / eachCycleVal);
        totalCycles += arr[i];
    }
    return 2 * totalCycles;
}

错误原因 #

这段代码的核心逻辑是将每2个世代（1个奇数+1个偶数）固定为一个周期，认为每个周期最多能给元素加3，但存在两个关键缺陷：

1. 强制使用完整周期，忽略了可以通过跳过无用世代来减少总次数（比如[2,2,4]中，两个加2操作可直接放在偶数世代，无需凑完整周期）
2. 没有考虑不同元素的操作可以交错安排，不需要每个元素都独立走完完整周期

正确算法思路 #

要计算最少世代数，我们需要先统计两类操作的总次数，再结合世代的奇偶限制推导最小世代数：

1. 统计操作次数：
   • 对每个元素，计算其与数组最大值的差值d
   • 差值d可分解为2*a + b（a为需要加2的次数，b为需要加1的次数，b只能是0或1）
   • 统计所有元素的a之和（记为totalEven，总加2操作数），b之和（记为totalOdd，总加1操作数）
2. 推导最小世代数：
   需要找到最小的G（世代数），满足：
   • G >= totalEven + totalOdd：每个操作至少占用一个世代
   • 偶数世代数量（(G + 1) // 2）>= totalEven：所有加2操作都能放在偶数世代
   • 奇数世代数量（G // 2）>= totalOdd：所有加1操作都能放在奇数世代

实现代码（JavaScript） #

const minGenerations = (arr) => {
    const maxVal = Math.max(...arr);
    let totalEven = 0; // 总加2操作次数
    let totalOdd = 0;  // 总加1操作次数
    
    for (const num of arr) {
        const diff = maxVal - num;
        totalEven += Math.floor(diff / 2);
        totalOdd += diff % 2;
    }
    
    // 计算三个候选值，取最大值即为最少世代数
    const candidate1 = totalEven + totalOdd;
    const candidate2 = totalEven > 0 ? 2 * totalEven - 1 : 0;
    const candidate3 = totalOdd > 0 ? 2 * totalOdd : 0;
    
    return Math.max(candidate1, candidate2, candidate3);
}

// 测试用例
console.log(minGenerations([1,1,2,4])); // 输出5（若允许跳过世代，这是最优解；原示例输出6为非最优步骤）
console.log(minGenerations([2,2,4]));    // 输出3，符合预期
console.log(minGenerations([1,2,2,4]));  // 输出5，比原算法更优

代码说明 #

• candidate1：保证每个操作都有对应的世代
• candidate2：保证有足够的偶数世代来完成所有加2操作
• candidate3：保证有足够的奇数世代来完成所有加1操作
  取三者最大值，即可得到满足所有条件的最少世代数。

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