企业官网建设流程全解析

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完整代码如下：

packagemainimport("fmt")constmx=100_001vardivisors[mx][]intfuncinit(){fori:=1;i<mx;i++{forj:=i;j<mx;j+=i{// 枚举 i 的倍数 jdivisors[j]=append(divisors[j],i)// i 是 j 的因子}}}funcminArraySum(nums[]int)(ansint64){cnt:=map[int]int{}for_,x:=rangenums{cnt[x]++}forx,c:=rangecnt{// 遍历 cnt 而不是 nums，这样重复元素只会计算一次for_,d:=rangedivisors[x]{// 从小到大枚举 x 的因子 difcnt[d]>0{ans+=int64(d)*int64(c)// 把 x 变成 d 是最优的break}}}return}funcmain(){nums:=[]int{3,6,2}result:=minArraySum(nums)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromcollectionsimportCounter MX=100_001divisors=[[]for_inrange(MX)]# 预处理因子：divisors[j] 保存 j 的所有因子，且按从小到大排列foriinrange(1,MX):forjinrange(i,MX,i):divisors[j].append(i)defmin_array_sum(nums):cnt=Counter(nums)ans=0forx,cincnt.items():fordindivisors[x]:# 从小到大枚举 x 的因子ifcnt[d]>0:ans+=d*c# 把 x 变成 dbreakreturnansdefmain():nums=[3,6,2]result=min_array_sum(nums)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<unordered_map>usingnamespacestd;constintMX=100001;vector<vector<int>>divisors(MX);voidinit_divisors(){for(inti=1;i<MX;++i){for(intj=i;j<MX;j+=i){// 枚举 i 的倍数 jdivisors[j].push_back(i);// i 是 j 的因子}}}longlongminArraySum(constvector<int>&nums){unordered_map<int,int>cnt;for(intx:nums){cnt[x]++;}longlongans=0;for(constauto&[x,c]:cnt){for(intd:divisors[x]){// 从小到大枚举 x 的因子autoit=cnt.find(d);if(it!=cnt.end()&&it->second>0){ans+=1LL*d*c;// 把 x 变成 dbreak;}}}returnans;}intmain(){init_divisors();vector<int>nums={3,6,2};longlongresult=minArraySum(nums);cout<<result<<endl;return0;}