2026-08-29：使数组变为模交替数组的最少操作次数Ⅰ。用go语言，有一个整数数组 nums 和一个整数 k。每次操作可以任选数组中的一个元素，

2026-08-29：使数组变为模交替数组的最少操作次数Ⅰ。用go语言，有一个整数数组 nums 和一个整数 k。每次操作可以任选数组中的一个元素，把它加 1 或减 1，花费 1 次操作。

如果存在两个不同的整数 x 和 y，且 x 和 y 都在 0 到 k-1 之间，使得数组所有偶数下标位置的元素对 k 取模后都等于 x，同时所有奇数下标位置的元素对 k 取模后都等于 y，那么就称这个数组是满足条件的。

问：最少需要多少次增减操作，才能使给定的数组变成满足条件的数组？返回这个最少操作次数。

1 <= nums.length <= 100。

1 <= nums[i] <= 1000000000。

2 <= k <= 100。

输入： nums = [1,4,2,8], k = 3。

输出： 2。

解释：

让我们为偶数下标选择 x = 1 ，为奇数下标选择 y = 2 。

执行以下操作：

将 nums[1] = 4 增加 1 ，得到 nums = [1, 5, 2, 8] 。

将 nums[2] = 2 减少 1 ，得到 nums = [1, 5, 1, 8] 。

现在，对于偶数下标，nums[i] % k = 1 ，对于奇数下标，nums[i] % k = 2 。

因此，所需的总操作次数为 2 。

题目来自力扣3937。

解题思路整体概述

本题要求将数组按奇偶下标分成两组，分别选定一个模k的余数（偶数下标选定x，奇数下标选定y，且x ≠ y），使得两组元素各自通过“加 1 或减 1”操作变成目标余数的总操作数最小。由于每次操作只改变数值 1，且最终只需满足模k的余数等于目标值，因此对于每个原始数值，我们可以自由调整其整数倍部分，操作次数只与它在“模k的圆环”上到目标余数的最短距离有关。这样问题就退化成了：对于一组余数（0 到k-1），选取一个目标余数，使所有余数到该目标（允许跨周期）的圆环距离之和最小。

算法主体分为三部分：分组、单组最优计算（calc）、合并两组结果。

一、分组

• 遍历整个nums数组，根据下标奇偶性分别收集每个元素对k取模后的余数。

• 得到两个列表：even（偶数下标）和odd（奇数下标）。

• 如果数组长度为 1，则无需任何操作，直接返回 0（因为此时奇偶下标无法同时存在，但题目默认可接受）。

二、单组最优计算（calc函数）

输入是一个长度n的余数列表a（每个值在[0, k-1]），输出三个信息：

•mn：该组所有元素变成某个余数的最小总操作数；

•mn2：该组所有元素变成另一个不同余数的次小总操作数（即第二小的总操作数）；

•bestX：取得最小值时对应的那个余数。

2.1 排序与扩展

• 先将列表a升序排序。

• 构造扩展数组ext，包含原排序数组的每个元素，以及每个元素加上k后的值（即a[i] + k）。这样ext的长度为2n，它相当于把余数放在数轴上，并复制了一份向右平移一个周期。

2.2 计算前缀和

• 对ext求前缀和，方便后续快速求区间和。

2.3 定义计算函数calcOp(target)

该函数计算：将原数组a（即排序后的前n个元素）全部变成target（模k意义下）所需的最小总操作数。

具体做法：

• 在排序后的原数组（前n个元素）中二分查找第一个>= target的位置，记为i。

• 在扩展数组的区间[i, i+n)内（即从i开始，连续取n个元素）二分查找第一个>= target + k/2 + 1的位置，记为j。这里target + k/2 + 1是分界点，因为对于余数v，它离target更近还是离target + k更近的分界点大约在target + k/2处。

• 将窗口[i, i+n)分为两段：

• 左段[i, j)：这些数离target更近，将它们都减小到target，所需操作数为(区间和) - (区间长度) * target。

• 右段[j, i+n)：这些数离target + k更近，将它们都增大到target + k，所需操作数为(区间长度) * (target + k) - (区间和)。

• 两段操作数之和即为calcOp(target)的返回值。

注意：这里隐含了每个元素最终变成 target 或 target+k，而不会考虑 target-k，因为对于原始余数在 [0, k-1] 内，target-k 离得更远，不会是最优选择。

2.4 遍历候选余数并维护最小和次小

• 遍历排序后的原数组a[:n]，跳过重复值（相同的余数不会产生更优结果）。

• 对每个不同的余数x调用calcOp(x)，得到操作数op。

• 用op更新全局最小mn和次小mn2，同时记录取得最小值的余数bestX。

• 遍历结束后，再额外考虑bestX的两个相邻余数（(bestX-1+k)%k和(bestX+1)%k），因为最优目标可能不在原始数据点上，而可能出现在其相邻位置。对这两个候选值调用calcOp，仅用于更新次小值mn2（确保最小值的候选余数仍然为bestX）。

2.5 返回结果

返回(mn, mn2, bestX)。

三、合并两组结果

• 分别对even和odd调用calc，得到：

• 偶数组的(min1x, min2x, bestX)

• 奇数组的(min1y, min2y, bestY)

• 若bestX != bestY，说明可以分别取这两个不同的余数，总操作数为min1x + min1y，直接返回。

• 若bestX == bestY，则必须让其中一个组放弃最优解，改用次优解，以保证两个目标余数不同。此时总操作数有两种可能：

1. 偶数用最优，奇数用次优：min1x + min2y

2. 偶数用次优，奇数用最优：min2x + min1y
取两者较小值返回。

四、时间与空间复杂度

•时间复杂度：

• 单次calc内排序为O(n log n)，遍历不同余数最多n次，每次calcOp内部执行两次二分查找，每次O(log n)，故单组计算为O(n log n)。

• 主函数对偶、奇两组各调用一次，整体复杂度为O(N log N)，其中N是数组长度（N ≤ 100），常数极小。

•额外空间复杂度：

•calc中需要存储扩展数组ext（长度2n）和前缀和数组（长度2n+1），以及排序后的原数组，均为O(n)。

• 主函数中存储偶、奇两组也各为O(N)。

• 总额外空间为O(N)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
    "slices"
    "sort"
)

 func calc(a []int, k int) (int, int, int) {
    n := len(a)
    slices.Sort(a)
    for _, x := range a {
        a = append(a, x+k)
    }

     sum := make([]int, n*2+1)
    for i, x := range a {
        sum[i+1] = sum[i] + x
    }

     // 都变成 target 的最小操作次数
    calcOp := func(target int) int {
        i := sort.SearchInts(a[:n], target)
        j := i + sort.SearchInts(a[i:i+n], target+k/2+1)
        return (sum[j] - sum[i]) - (j-i)*target + // [i, j) 中的数都减小到 target
            (n-j+i)*(target+k) - (sum[i+n] - sum[j]) // [j, i+n) 中的数都增大到 target+k
    }

     mn, mn2, bestX := math.MaxInt, math.MaxInt, 0
    for i, x := range a[:n] {
        if i > 0 && a[i] == a[i-1] { // 优化：相同的值无需重复计算
            continue
        }
        op := calcOp(x)
        // 维护最小次小操作次数
        if op < mn {
            mn2 = mn
            mn, bestX = op, x
        } else if op < mn2 {
            mn2 = op
        }
    }

     // 还可以都变成 bestX-1 或者 bestX+1
    mn2 = min(mn2, calcOp((bestX-1+k)%k), calcOp((bestX+1)%k))

     return mn, mn2, bestX
}

 func minOperations(nums []int, k int) int {
    if len(nums) == 1 {
        return 0
    }

     a := [2][]int{}
    for i, x := range nums {
        a[i%2] = append(a[i%2], x%k)
    }

     min1x, min2x, bestX := calc(a[0], k)
    min1y, min2y, bestY := calc(a[1], k)

     if bestX != bestY {
        return min1x + min1y
    }
    return min(min1x+min2y, min2x+min1y)
}

 func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 func main() {
    nums := []int{1, 4, 2, 8}
    k := 3
    result := minOperations(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import bisect
import math

 def calc(a, k):
    # a 是已经取模后的余数列表（非空）
    n = len(a)
    a_sorted = sorted(a)
    # 扩展数组，用于处理跨周期
    ext = a_sorted + [x + k for x in a_sorted]
    prefix = [0] * (len(ext) + 1)
    for i, v in enumerate(ext):
        prefix[i + 1] = prefix[i] + v

     def calc_op(target):
        # 将数组 a 中所有数变成 target（模 k）所需的最小操作数
        i = bisect.bisect_left(a_sorted, target)
        # 在 ext[i : i+n] 中找第一个 >= target + k//2 + 1 的位置
        j = bisect.bisect_left(ext, target + k // 2 + 1, i, i + n)
        cnt1 = j - i
        sum1 = prefix[j] - prefix[i]
        cnt2 = n - cnt1
        sum2 = prefix[i + n] - prefix[j]
        # 前半部分减小到 target，后半部分增大到 target+k
        ops = (sum1 - cnt1 * target) + (cnt2 * (target + k) - sum2)
        return ops

     mn = math.inf
    mn2 = math.inf
    best_x = 0

     # 遍历所有不同的余数值作为候选 target
    prev = None
    for x in a_sorted:
        if x == prev:
            continue
        prev = x
        op = calc_op(x)
        if op < mn:
            mn2 = mn
            mn = op
            best_x = x
        elif op < mn2:
            mn2 = op

     # 再尝试 best_x 的相邻值（模 k 意义下）
    for delta in (-1, 1):
        cand = (best_x + delta) % k
        op = calc_op(cand)
        if op < mn:
            mn2 = mn
            mn = op
            best_x = cand
        elif op < mn2:
            mn2 = op

     return mn, mn2, best_x

 def minOperations(nums, k):
    if len(nums) == 1:
        return 0

     even = [nums[i] % k for i in range(0, len(nums), 2)]
    odd  = [nums[i] % k for i in range(1, len(nums), 2)]

     min1x, min2x, best_x = calc(even, k)
    min1y, min2y, best_y = calc(odd, k)

     if best_x != best_y:
        return min1x + min1y
    else:
        return min(min1x + min2y, min2x + min1y)

 # 测试示例
if __name__ == "__main__":
    nums = [1, 4, 2, 8]
    k = 3
    print(minOperations(nums, k)) 

C++完整代码如下：

  

  

    

  

using namespace std;


 // 返回：最小操作数，次小操作数，最佳余数
tuple 
 
 int 
 > calc(vector< 
 int 
 > a,  
 int 
  k) { 
 
 
      
 int 
  n = a.size(); 
 
 
     sort(a.begin(), a.end()); 
 
 
 
 
      
 // 扩展：每个数加 k 放到末尾，便于处理周期 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < n; ++i) { 
 
 
         a.push_back(a[i] + k); 
 
 
     } 
 
 
 
 
      
 // 前缀和（长整型） 
 
 
     vector 
 
 sum( 
 
 2 
  * n +  
 1 
 ,  
 0 
 ); 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i <  
 2 
  * n; ++i) { 
 
 
         sum[i +  
 1 
 ] = sum[i] + a[i]; 
 
 
     } 
 
 
 
 
      
 // 计算将所有数变为模 k 等于 target 的最小操作数 
 
 
     auto calcOp = [&]( 
 int 
  target) -> long long { 
 
 
          
 // 原数组（前 n 个）中第一个 >= target 的位置 
 
 
          
 int 
  i = lower_bound(a.begin(), a.begin() + n, target) - a.begin(); 
 
 
          
 // 在扩展数组的 [i, i+n) 区间中找第一个 >= target + k/2 + 1 的位置 
 
 
          
 int 
  j = i + (lower_bound(a.begin() + i, a.begin() + i + n, 
 
 
                                  target + k /  
 2 
  +  
 1 
 ) - (a.begin() + i)); 
 
 
          
 // 左半部分（[i, j)）缩小到 target，右半部分（[j, i+n)）增大到 target+k 
 
 
         long long ops = (sum[j] - sum[i]) - (long long)(j - i) * target 
 
 
                         + (long long)(n - j + i) * (target + k) - (sum[i + n] - sum[j]); 
 
 
          
 return 
  ops; 
 
 
     }; 
 
 
 
 
     long long mn = LLONG_MAX, mn2 = LLONG_MAX; 
 
 
      
 int 
  bestX =  
 0 
 ; 
 
 
 
 
      
 // 遍历所有不同的余数值作为候选 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < n; ++i) { 
 
 
          
 if 
  (i >  
 0 
  && a[i] == a[i -  
 1 
 ])  
 continue 
 ;    
 // 跳过重复值 
 
 
          
 int 
  x = a[i]; 
 
 
         long long op = calcOp(x); 
 
 
          
 if 
  (op < mn) { 
 
 
             mn2 = mn; 
 
 
             mn = op; 
 
 
             bestX = x; 
 
 
         }  
 else 
   
 if 
  (op < mn2) { 
 
 
             mn2 = op; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 // 再尝试 bestX 的相邻值（模 k 意义下） 
 
 
      
 int 
  cand1 = (bestX -  
 1 
  + k) % k; 
 
 
      
 int 
  cand2 = (bestX +  
 1 
 ) % k; 
 
 
     mn2 = min(mn2, calcOp(cand1)); 
 
 
     mn2 = min(mn2, calcOp(cand2)); 
 
 
 
 
      
 return 
  {mn, mn2, bestX}; 
 
 
 } 
 
 
 
 
 long long minOperations(vector< 
 int 
 >& nums,  
 int 
  k) { 
 
 
      
 if 
  (nums.size() ==  
 1 
 )  
 return 
   
 0 
 ; 
 
 
 
 
     vector< 
 int 
 > even, odd; 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < ( 
 int 
 )nums.size(); ++i) { 
 
 
          
 if 
  (i %  
 2 
  ==  
 0 
 ) even.push_back(nums[i] % k); 
 
 
          
 else 
  odd.push_back(nums[i] % k); 
 
 
     } 
 
 
 
 
     auto [min1x, min2x, bestX] = calc(even, k); 
 
 
     auto [min1y, min2y, bestY] = calc(odd, k); 
 
 
 
 
      
 if 
  (bestX != bestY) { 
 
 
          
 return 
  min1x + min1y; 
 
 
     }  
 else 
  { 
 
 
          
 return 
  min(min1x + min2y, min2x + min1y); 
 
 
     } 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > nums = { 
 1 
 ,  
 4 
 ,  
 2 
 ,  
 8 
 }; 
 
 
      
 int 
  k =  
 3 
 ; 
 
 
     cout << minOperations(nums, k) << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。