2026-08-22：可整除替换后的数组最小元素和。用go语言，给定一个整数数组。你可以反复执行这种操作：任意选出两个位置，如果其中一个位置

2026-08-22：可整除替换后的数组最小元素和。用go语言，给定一个整数数组。你可以反复执行这种操作：任意选出两个位置，如果其中一个位置上的数能被另一个位置上的数整除，就把那个“倍数”位置的数改成“除数”位置的数。每次替换后，被改动的数只会变小或保持不变。请问经过任意多次这样的操作，整个数组所有数的总和最小可以变成多少？

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入： nums = [3,6,2]。

输出： 7。

解释：

选择 a = 1、b = 2，此时 nums[a] = 6，nums[b] = 2。由于 6 % 2 == 0，将 nums[1] 替换为 nums[2]。

数组变为 [3, 2, 2]。

之后无法再通过操作减少元素和。因此，最终元素和为 3 + 2 + 2 = 7。

题目来自力扣3927。

分步骤详解 第一步：预处理所有数的因子表

• 代码中定义了一个全局的二维切片divisors，大小为 100001（因为题目限制 nums[i] ≤ 100000）。

• 在init函数中，枚举：

• 外层循环 i 从 1 到 100000

• 内层循环 j 从 i 开始，每次增加 i，直到超过 100000

• 对于每个 j，把 i 追加到divisors[j]中，表示 i 是 j 的一个因子

• 例如：

• 当 i=1，会把 1 加到所有 1~100000 的因子列表里

• 当 i=2，会把 2 加到 2,4,6,8,… 的因子列表里

• 结果：divisors[x]里存放的是 x 的所有正因子，并且是按从小到大顺序存放的（因为外层 i 从小到大）。

第二步：统计数组元素出现次数

• 使用一个字典cnt（map[int]int）来统计每个数字在数组中出现的次数。

• 这样做的目的：相同的数字操作结果一样，无需重复计算，可以节省时间。

第三步：遍历每个不同的数字，找到它能变成的最小可行值

• 对于cnt中的每个键x及其出现次数c：

• 我们想要把当前所有值为 x 的元素，替换成某个更小的数，并且这个数必须是数组中存在的（因为要作为“除数”）。

• 因为因子列表是按从小到大的顺序，我们直接遍历divisors[x]，检查该因子是否在cnt中存在（即数组里有这个数）。

• 一旦找到第一个存在的因子d，就可以将所有这 c 个 x 都替换成 d，因为 d ≤ x，且这是能取得的最小可行替换值（因子从小到大）。

• 累加ans += d * c，然后立即跳出循环（因为只需最小的那个因子即可）。

关键点：

• 如果一个数 x 最小的因子 1 在数组中存在，那么它可以直接变成 1，这是最优的。

• 如果 x 本身就在数组中（即因子 x 存在），其实它在遍历因子时最早遇到的是 1（如果1存在），否则可能遇到更小的因子，但最差就是因子 x 本身（此时替换成自己，不变）。

第四步：返回最小总和

• 累加完所有不同数字对应的最小可能值乘以其出现次数，就得到了整个数组的最小总和。

示例运行过程（nums=[3,6,2]）

1. 统计：cnt = {3:1, 6:1, 2:1}

2. 处理 x=3：

• 因子列表：1,3

• 检查1是否在cnt → 不存在

• 检查3是否在cnt → 存在，所以变成3，ans += 3

3. 处理 x=6：

• 因子列表：1,2,3,6

• 检查1 → 不存在

• 检查2 → 存在，变成2，ans += 2

4. 处理 x=2：

• 因子列表：1,2

• 检查1 → 不存在

• 检查2 → 存在，变成2，ans += 2

5. 最终 ans = 3+2+2 = 7

时间复杂度分析

•预处理因子表：

• 双层循环：外层 100000 次，内层总迭代次数约为n * (1/1 + 1/2 + ... + 1/n)≈ n log n。

• 这里 n=100000，所以大约 100000 * log(100000) ≈ 1.2e6 次操作，非常快。

•统计次数：O(N)，N 是数组长度，最多 100000。

•每个不同数字查找最小因子：

• 最坏情况，每个数要遍历它的所有因子。所有不同数字的总因子数量，就是所有出现过的数字的因子个数总和。

• 在最坏情况下（数组包含 1~100000 的所有数），因子总数同样约为 N log N。

• 且每个因子检查只是 map 查找 O(1)。

•总时间复杂度：预处理 O(M log M) + 主逻辑 O(M log M)（M=100000），即O(M log M)，其中 M 是数值上限（100000），与数组长度 N 和数值范围有关。

额外空间复杂度分析

•divisors二维切片：

• 存储所有数的所有因子，总数量约为 M log M ≈ 1.2e6 个整数，占用空间 O(M log M)。

•cntmap：

• 最多存放不同数字个数 ≤ min(N, M)，空间 O(min(N, M))。

• 总体额外空间：O(M log M)，因为预处理表是主要占用。

最终答案总结：

• 算法通过预处理因子表并利用出现次数字典，对每个不同的数找到数组中出现的最小因子来进行替换，保证总和最小。

• 时间复杂度：O(M log M)（M=100000，近乎常数规模）

• 额外空间复杂度：O(M log M)

Go完整代码如下：

package main

 import (
    "fmt"
)

 const mx = 100_001

 var divisors [mx][]int

 func init() {
    for i := 1; i < mx; i++ {
        for j := i; j < mx; j += i { // 枚举 i 的倍数 j
            divisors[j] = append(divisors[j], i) // i 是 j 的因子
        }
    }
}

 func minArraySum(nums []int) (ans int64) {
    cnt := map[int]int{}
    for _, x := range nums {
        cnt[x]++
    }

     for x, c := range cnt { // 遍历 cnt 而不是 nums，这样重复元素只会计算一次
        for _, d := range divisors[x] { // 从小到大枚举 x 的因子 d
            if cnt[d] > 0 {
                ans += int64(d) * int64(c) // 把 x 变成 d 是最优的
                break
            }
        }
    }
    return
}

 func main() {
    nums := []int{3, 6, 2}
    result := minArraySum(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

 from collections import Counter

 MX = 100_001
divisors = [[] for _ in range(MX)]

 # 预处理因子：divisors[j] 保存 j 的所有因子，且按从小到大排列
for i in range(1, MX):
    for j in range(i, MX, i):
        divisors[j].append(i)

 def min_array_sum(nums):
    cnt = Counter(nums)
    ans = 0

     for x, c in cnt.items():
        for d in divisors[x]:  # 从小到大枚举 x 的因子
            if cnt[d] > 0:
                ans += d * c   # 把 x 变成 d
                break

     return ans

 def main():
    nums = [3, 6, 2]
    result = min_array_sum(nums)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

#include  

#include  

#include  

using namespace std;


 const int MX = 100001;
vector 
 
 int 
 >>  
 divisors 
 (MX); 
 
 
 
 
 void init_divisors()  
 { 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i < MX; ++i) { 
 
 
          
 for 
  ( 
 int 
  j = i; j < MX; j += i) {   
 // 枚举 i 的倍数 j 
 
 
             divisors[j]. 
 push_back 
 (i);       
 // i 是 j 的因子 
 
 
         } 
 
 
     } 
 
 
 } 
 
 
 
 
 long long minArraySum(const vector& nums)  
 { 
 
 
     unordered_map< 
 int 
 ,  
 int 
 > cnt; 
 
 
      
 for 
  ( 
 int 
  x : nums) { 
 
 
         cnt[x]++; 
 
 
     } 
 
 
 
 
      
 long 
   
 long 
  ans =  
 0 
 ; 
 
 
      
 for 
  ( 
 const 
   
 auto 
 & [x, c] : cnt) { 
 
 
          
 for 
  ( 
 int 
  d : divisors[x]) {   
 // 从小到大枚举 x 的因子 
 
 
              
 auto 
  it = cnt. 
 find 
 (d); 
 
 
              
 if 
  (it != cnt. 
 end 
 () && it->second >  
 0 
 ) { 
 
 
                 ans +=  
 1LL 
  * d * c;    
 // 把 x 变成 d 
 
 
                  
 break 
 ; 
 
 
             } 
 
 
         } 
 
 
     } 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int main()  
 { 
 
 
      
 init_divisors 
 (); 
 
 
     vector< 
 int 
 > nums = { 
 3 
 ,  
 6 
 ,  
 2 
 }; 
 
 
      
 long 
   
 long 
  result =  
 minArraySum 
 (nums); 
 
 
     cout << result << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 

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