2026-07-27：连接二进制片段得到的最大值。用go语言，给定两个长度为 n 的整数数组 nums1 和 nums0，其中 nums1[i] 代表第 i 个片段中 ‘1‘ 的个数，nums0[i]

2026-07-27：连接二进制片段得到的最大值。用go语言，给定两个长度为 n 的整数数组 nums1 和 nums0，其中 nums1[i] 代表第 i 个片段中 ‘1’ 的个数，nums0[i] 代表该片段中 ‘0’ 的个数。对于每个 i，我们构造一个二进制片段：先写入 nums1[i] 个连续的 ‘1’，紧接着写入 nums0[i] 个连续的 ‘0’。我们可以将这些片段以任意顺序重新排列，然后将排列后的所有片段依次拼接成一个完整的二进制字符串。要求找出在所有可能的排列方式中，该二进制字符串所能表示的最大整数值。由于答案可能很大，请将其对 1000000007 取模后返回。

1 <= n == nums1.length == nums0.length <= 100000。

0 <= nums1[i], nums0[i] <= 10000。

nums1[i] + nums0[i] > 0。

nums1 和 nums0 中所有元素的总和不超过 200000。

输入： nums1 = [1,2], nums0 = [1,0]。

输出： 14。

解释：

在下标 0 处，nums1[0] = 1 且 nums0[0] = 1，因此形成的片段为 “10”。

在下标 1 处，nums1[1] = 2 且 nums0[1] = 0，因此形成的片段为 “11”。

将片段重新排序为 “11” 后跟 “10”，生成二进制字符串 “1110”。

二进制数 “1110” 的值为 14，这是可能的最大值。

题目来自力扣3897。

大体步骤如下：

1. 预处理：计算2的幂次方

• 目的：由于在后续计算中需要频繁地计算2^k mod MOD（其中k是每个片段中 ‘1’ 或 ‘0’ 的数量），提前预处理好这些值可以避免重复计算，大大提高效率。
• 过程：创建一个大小为mx（10001）的数组pow2。
  • pow2[0]初始化为 1（代表2^0）。
  • 通过一个循环，利用递推关系pow2[i] = (pow2[i-1] * 2) % MOD，计算出从2^1到2^10000的所有值并存储起来。

2. 确定片段的最佳拼接顺序

这是算法的核心。目标是找出一种排列顺序，使得最终拼接成的二进制字符串表示的数值最大。

• 初始化：创建一个索引数组idx，长度等于片段总数n，并填入0到n-1的序号。这个数组用于后续的排序，我们不是直接移动原始的片段数据，而是对它们的索引进行排序。

• 自定义排序规则：我们需要定义一种比较逻辑，来判断任意两个片段A和B，谁排在前面能使最终结果更大。这里的比较策略非常巧妙：

  1. 特殊情况处理：比较片段i和片段j。
     • 规则1：如果片段i的 ‘0’ 的个数为 0（nums0[i] == 0），那么这个片段应该排在任何带有 ‘0’ 的片段（nums0[j] > 0）之前。一个纯 ‘1’ 的片段放在前面，可以确保它的高位全是 ‘1’，从而最大化整个数值。
     • 规则2（规则1的补充）：如果片段j的 ‘0’ 的个数为 0，那么它应该排在片段i之前。
  2. 一般情况比较：如果两个片段都包含至少一个 ‘0’（即nums0[i] > 0且nums0[j] > 0），则我们需要一个通用的比较方法。
     • 我们实际上是在比较两种拼接方案：片段i + 片段j和片段j + 片段i，哪个更大。
     • 可以证明，这种比较可以转化为优先比较两个片段中 ‘1’ 的个数。具体来看：首先比较nums1[j]和nums1[i]的差值。如果nums1[j] - nums1[i] != 0，则意味着一个片段的 ‘1’ 比另一个多。拥有更多 ‘1’ 的片段应排在前面，因为它能为高位贡献更多的 ‘1’。
     • 如果两个片段的 ‘1’ 的个数完全相同（nums1[j] == nums1[i]），那么就需要比较它们 ‘0’ 的个数。此时，包含更少‘0’ 的片段应排在前面。因为更少的 ‘0’ 意味着这个片段的结束部分会更短，能更快地过渡到下一个片段的 ‘1’，避免在数值的高位部分留下过多的 ‘0’。
  • 排序执行：使用这个复杂的自定义比较规则，对索引数组idx进行排序。排序后，idx数组中的索引顺序就代表了片段的最佳拼接顺序。

3. 迭代计算最终的最大值

在得到了最佳拼接顺序（即idx数组）后，我们模拟拼接过程，逐步计算出最终数值的十进制表示（对MOD取模）。

• 初始化答案ans为 0。
• 按最优顺序遍历片段：依次取出idx中的索引i。
• 状态转移（核心公式）：
  • 假设当前已拼接好的前缀字符串对应的数值是ans。
  • 下一个要拼接的片段包含ones（nums1[i]）个 ‘1’ 和zeros（nums0[i]）个 ‘0’。
  • 步骤3.1（追加’1’s）：将当前值ans左移ones位（相当于乘以2^ones），然后追加ones个 ‘1’。这ones个 ‘1’ 代表的数值是(2^ones - 1)。因此，这一步操作可以表达为：新值 = ans * (2^ones) + (2^ones - 1)。代码中巧妙地将其合并为(ans + 1) * pow2[ones] - 1。
  • 步骤3.2（追加’0’s）：在步骤3.1的结果后面再追加zeros个 ‘0’。这相当于将当前值左移zeros位（相当于乘以2^zeros）。因此，这一步操作表达为：最终新值 = 步骤3.1的结果 * pow2[zeros]。
  • 取模：每一步计算新值时，都对MOD进行取模运算，确保ans不会溢出，且满足题目要求。
• 完成：遍历完所有片段后，最终的ans就是所求的最大整数值。

---

复杂度分析

• 总的时间复杂度：O(n log n + M)

  • M是mx，即 10001。预处理pow2数组的时间复杂度是 O(M)。
  • 排序索引数组idx的时间复杂度是 O(n log n)，n是片段的数量。
  • 迭代计算最终值的过程是 O(n)。
  • 主要瓶颈在于排序，因此总时间复杂度为 O(n log n + M)。

• 总的额外空间复杂度：O(n + M)

  • pow2数组的大小固定为M（10001），空间复杂度为 O(M)。
  • 索引数组idx的长度为n，空间复杂度为 O(n)。
  • 其他变量使用的空间是常数级。
  • 因此，总的额外空间需求是 O(n + M)。

Go完整代码如下：

packagemainimport("cmp""fmt""slices")constmod=1_000_000_007constmx=10001varpow2=[mx]int{1}funcinit(){// 预处理 2 的幂fori:=1;i<mx;i++{pow2[i]=pow2[i-1]*2%mod}}funcmaxValue(nums1,nums0[]int)(ansint){idx:=make([]int,len(nums1))fori:=rangeidx{idx[i]=i}slices.SortFunc(idx,func(i,jint)int{ifnums0[i]==0{return-1}ifnums0[j]==0{return1}returncmp.Or(nums1[j]-nums1[i],nums0[i]-nums0[j])})for_,i:=rangeidx{ans=((ans+1)*pow2[nums1[i]]-1)%mod*pow2[nums0[i]]%mod}return}funcmain(){nums1:=[]int{1,2}nums0:=[]int{1,0}result:=maxValue(nums1,nums0)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-MOD=1_000_000_007MX=10001# 预处理 2 的幂pow2=[1]*MXforiinrange(1,MX):pow2[i]=pow2[i-1]*2%MODdefmaxValue(nums1,nums0):n=len(nums1)idx=list(range(n))# 自定义排序函数defsort_key(i):ifnums0[i]==0:return(0,0,0)# 负数标记，排最前面ifnums0[j]==0:# 这个在排序比较中无法直接使用，需要改为cmp方式return(2,0,0)# 正数标记，排最后面# 使用functools.cmp_to_key来实现自定义比较fromfunctoolsimportcmp_to_keydefcmp_func(i,j):ifnums0[i]==0:return-1ifnums0[j]==0:return1# cmp.Or(nums1[j]-nums1[i], nums0[i]-nums0[j])diff1=nums1[j]-nums1[i]ifdiff1!=0:returndiff1returnnums0[i]-nums0[j]idx.sort(key=cmp_to_key(cmp_func))ans=0foriinidx:ans=((ans+1)*pow2[nums1[i]]-1)%MOD*pow2[nums0[i]]%MODreturnansdefmain():nums1=[1,2]nums0=[1,0]result=maxValue(nums1,nums0)print(result)if__name__=="__main__":main()

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<functional>constintMOD=1'000'000'007;constintMX=10001;// 预处理 2 的幂std::vector<int>pow2(MX);voidinit(){pow2[0]=1;for(inti=1;i<MX;i++){pow2[i]=(pow2[i-1]*2LL)%MOD;}}intmaxValue(conststd::vector<int>&nums1,conststd::vector<int>&nums0){intn=nums1.size();std::vector<int>idx(n);for(inti=0;i<n;i++){idx[i]=i;}// 自定义排序std::sort(idx.begin(),idx.end(),[&](inti,intj){if(nums0[i]==0){returntrue;// i 排在前面}if(nums0[j]==0){returnfalse;// j 排在前面}// cmp.Or(nums1[j]-nums1[i], nums0[i]-nums0[j])intdiff1=nums1[j]-nums1[i];if(diff1!=0){returndiff1<0;// nums1[i] > nums1[j] 时 i 排在前面}returnnums0[i]-nums0[j]<0;});longlongans=0;for(inti:idx){ans=(((ans+1)*pow2[nums1[i]]-1)%MOD)*pow2[nums0[i]]%MOD;ans=(ans+MOD)%MOD;// 确保结果为正}returnstatic_cast<int>(ans);}intmain(){// 初始化pow2数组init();std::vector<int>nums1={1,2};std::vector<int>nums0={1,0};intresult=maxValue(nums1,nums0);std::cout<<result<<std::endl;return0;}