线性动态规划：使数组变成交替数组的最少操作次数 题目描述 给定一个整数数组 nums ，你可以选择任意一个元素并将其值改为任意整数（操作次数+1）。我们的目标是使数组变成“交替数组”。交替数组的定义是：数组中所有奇数索引位置的元素都相等，所有偶数索引位置的元素也都相等，但这两个值不能相同。 请你计算将 nums 变成交替数组所需的最少操作次数。 示例： 输入：nums = [ 3,1,3,2,4,3 ] 输出：3 解释：一种可行方案是将数组变为 [ 3,3,3,3,3,3]，但这不是交替数组（奇偶位置值相同，不符合要求）。正确方案是变为 [ 3,2,3,2,3,2 ]，需要修改索引1、3、5的元素，共3次操作。 解题过程 步骤1：理解问题结构 数组交替意味着偶数索引（0,2,4,...）全部是同一个值（记为 a ），奇数索引（1,3,5,...）全部是另一个值（记为 b ），且 a ≠ b 。 我们需要从 nums 中选出 a 和 b ，使得修改次数最少。修改次数 = 偶数索引中不是 a 的元素个数 + 奇数索引中不是 b 的元素个数。 关键： a 应该取偶数索引中出现频率最高的值（可最大化保留原有元素）， b 应该取奇数索引中出现频率最高的值，且 a ≠ b 。但如果最高频的 a 和 b 相同，我们需要考虑次高频的选择。 步骤2：统计频次 用两个字典分别记录偶数索引和奇数索引的元素出现次数。 同时记录每个索引位置的两个最高频元素及其频次（因为可能需退而求其次）。 步骤3：动态规划思想与选择策略 设偶数索引总数为 even_len ，奇数索引总数为 odd_len 。 如果偶数索引最高频元素 e1 （频次 f_e1 ）与奇数索引最高频元素 o1 （频次 f_o1 ）不同，则最优解为： 修改次数 = (even_len - f_e1) + (odd_len - f_o1) 如果 e1 == o1 ，则有两种可能： 偶数索引选 e1 ，奇数索引选次高频 o2 （若存在）：修改次数 = (even_len - f_e1) + (odd_len - f_o2) 偶数索引选次高频 e2 ，奇数索引选 o1 ：修改次数 = (even_len - f_e2) + (odd_len - f_o1) 取两种情况的较小值。 注意：如果某个索引位置所有元素相同（如奇数索引只有一种数值），且与偶数索引最高频冲突，则次高频频次为0。 步骤4：算法实现步骤 遍历数组，分别统计偶数索引和奇数索引的元素频次。 对两个频次字典按值降序排序，得到每个位置的前两个最高频元素及频次。 比较偶数索引和奇数索引的最高频元素： 若不同，直接计算最少操作次数。 若相同，则用上述两种替代方案计算，取最小值。 返回结果。 步骤5：示例演算 以nums = [ 3,1,3,2,4,3 ]为例： 偶数索引（0,2,4）：值[ 3,3,4] → 频次：{3:2, 4:1}，最高频e1=3（f_ e1=2），次高频e2=4（f_ e2=1） 奇数索引（1,3,5）：值[ 1,2,3] → 频次：{1:1, 2:1, 3:1}，最高频o1=3（f_ o1=1），但o1与e1相同，需看次高频（o2=1或2，f_ o2=1） 情况1：偶数选3，奇数选1（或2）→ 修改次数 = (3-2) + (3-1) = 1+2=3 情况2：偶数选4，奇数选3 → 修改次数 = (3-1) + (3-1) = 2+2=4 取最小值3，与示例一致。 总结 本题通过频次统计和贪心选择（优先保留高频元素）来最小化操作次数，动态规划思想体现在对多种选择策略的比较。关键点是处理奇偶索引最高频元素相同时的替代方案，确保交替数组的两个值不同。