Hard
题目描述
给你两个整数数组 nums1 和 nums0，每个数组的大小都是 n。
nums1[i]表示第i个段中 ‘1’ 的数量。nums0[i]表示第i个段中 ‘0’ 的数量。
对于每个索引 i，构造一个二进制段，包含：
nums1[i]个 ‘1’，然后是nums0[i]个 ‘0’。
你可以任意重新排列这些段的顺序。重新排列后，将所有段连接起来形成一个二进制字符串。
返回连接后的二进制字符串可能的最大整数值。
由于结果可能非常大，返回答案模 10^9 + 7。
示例 1：
输入：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，这是可能的最大值。
示例 2：
输入：nums1 = [3,1], nums0 = [0,3]
输出：120
解释：
- 在索引 0，nums1[0] = 3 且 nums0[0] = 0，所以形成的段是 "111"。
- 在索引 1，nums1[1] = 1 且 nums0[1] = 3，所以形成的段是 "1000"。
- 将段重新排列为 "111" 后跟 "1000" 产生二进制字符串 "1111000"。
- 二进制数 "1111000" 的值是 120，这是可能的最大值。
约束条件：
1 <= n == nums1.length == nums0.length <= 10^50 <= nums1[i], nums0[i] <= 10^4nums1[i] + nums0[i] > 0nums1和nums0中所有元素的总和不超过2 * 10^5
解题思路
这道题的关键在于找到最优的段排列顺序来使连接后的二进制字符串值最大。
核心思路：
为了使二进制字符串的值最大，我们需要让高位的比特为1。因此，包含更多1的段应该放在前面。
贪心策略：
按1的数量排序：初步想法是按
nums1[i]降序排列段。但这并不总是最优的，因为需要考虑段的总长度对后续段的影响。更精确的排序策略：关键观察是，当我们决定两个段A和B的相对顺序时，我们应该比较AB和BA两种排列的值。
- 如果段A有
a1个1和a0个0 - 如果段B有
b1个1和b0个0 - AB排列：A的贡献 + B左移
(a1+a0)位的贡献 - BA排列：B的贡献 + A左移
(b1+b0)位的贡献
- 如果段A有
比较准则：为了避免大数计算，我们可以通过数学推导得出：应该按照
nums1[i] * 2^(sum_others) - segment_value这样的优先级排序，但实际实现中，我们使用更直接的比较方法。
实现要点：
- 使用自定义比较器对段进行排序
- 计算最终的二进制值时需要模运算
- 使用快速幂计算2的幂次
代码实现
class Solution {
public:
int maxValue(vector<int>& nums1, vector<int>& nums0) {
const int MOD = 1e9 + 7;
int n = nums1.size();
vector<pair<int, int>> segments;
for (int i = 0; i < n; i++) {
segments.push_back({nums1[i], nums0[i]});
}
// 自定义排序：比较两个段AB和BA的值
sort(segments.begin(), segments.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
long long val_ab = 0, val_ba = 0;
int a1 = a.first, a0 = a.second;
int b1 = b.first, b0 = b.second;
// 计算AB排列的值 (简化版本，只比较关键部分)
// A的贡献 + B左移(a1+a0)位
for (int i = 0; i < a1; i++) {
val_ab += 1LL << (a0 + b1 + b0 + a1 - 1 - i);
}
for (int i = 0; i < b1; i++) {
val_ab += 1LL << (b0 + b1 - 1 - i);
}
// BA排列的值
for (int i = 0; i < b1; i++) {
val_ba += 1LL << (b0 + a1 + a0 + b1 - 1 - i);
}
for (int i = 0; i < a1; i++) {
val_ba += 1LL << (a0 + a1 - 1 - i);
}
return val_ab > val_ba;
});
// 计算最终结果
long long result = 0;
long long power = 1;
// 从右到左计算每个段的贡献
for (int i = n - 1; i >= 0; i--) {
int ones = segments[i].first;
int zeros = segments[i].second;
// 先处理0
for (int j = 0; j < zeros; j++) {
power = (power * 2) % MOD;
}
// 处理1
for (int j = 0; j < ones; j++) {
result = (result + power) % MOD;
power = (power * 2) % MOD;
}
}
return result;
}
};
class Solution:
def maxValue(self, nums1: list[int], nums0: list[int]) -> int:
MOD = 10**9 + 7
n = len(nums1)
segments = [(nums1[i], nums0[i]) for i in range(n)]
# 简化的排序策略：按1的数量降序，如果相等则按总长度升序
def compare_segments(a, b):
a1, a0 = a
b1, b0 = b
# 比较策略：优先考虑1的数量，然后考虑对后续段的影响
if a1 != b1:
return b1 - a1 # 1多的在前
return a0 - b0 # 如果1相等，0少的在前
from functools import cmp_to_key
segments.sort(key=cmp_to_key(compare_segments))
result = 0
power = 1
# 从右到左计算每个段的贡献
for i in range(n - 1, -1, -1):
ones, zeros = segments[i]
# 处理0
for _ in range(zeros):
power = (power * 2) % MOD
# 处理1
for _ in range(ones):
result = (result + power) % MOD
power = (power * 2) % MOD
return result
public class Solution {
public int MaxValue(int[] nums1, int[] nums0) {
const int MOD = 1000000007;
int n = nums1.Length;
var segments = new List<(int ones, int zeros)>();
for (int i = 0; i < n; i++) {
segments.Add((nums1[i], nums0[i]));
}
// 排序：按1的数量降序
segments.Sort((a, b) => {
if (a.ones != b.ones) {
return b.ones.CompareTo(a.ones);
}
return a.zeros.CompareTo(b.zeros);
});
long result = 0;
long power = 1;
// 从右到左计算每个段的贡献
for (int i = n - 1; i >= 0; i--) {
int ones = segments[i].ones;
int zeros = segments[i].zeros;
// 处理0
for (int j = 0; j < zeros; j++) {
power = (power * 2) % MOD;
}
// 处理1
for (int j = 0; j < ones; j++) {
result = (result + power) % MOD;
power = (power * 2) % MOD;
}
}
return (int)result;
}
}
var maxValue = function(nums1, nums0) {
const MOD = 1e9 + 7;
const n = nums1.length;
const segments = [];
for (let i = 0; i < n; i++) {
segments.push([nums1[i], nums0[i]]);
}
// 排序：按1的数量降序
segments.sort((a, b) => {
if (a[0] !== b[0]) {
return b[0] - a[0];
}
return a[1] - b[1];
});
let result = 0;
let power = 1;
// 从右到左计算每个段的贡献
for (let i = n - 1; i >= 0; i--) {
const ones = segments[i][0];
const zeros = segments[i][1];
// 处理0
for (let j = 0; j < zeros; j++) {
power = (power * 2) % MOD;
}
// 处理1
for (let j = 0; j < ones; j++) {
result = (result + power) % MOD;
power = (power * 2) % MOD;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n log n + S)，其中 n 是段的数量，S 是所有段的总长度 |
| 空间复杂度 | O(n)，用于存储段信息和排序 |