Hard
题目描述
给你一个下标从 0 开始的数组 nums，由非负的 2 的幂组成，以及一个整数 target。
在一次操作中，你必须对数组进行以下更改：
- 选择数组中任意一个元素
nums[i]，其中nums[i] > 1。 - 从数组中移除
nums[i]。 - 在数组末尾添加两个
nums[i] / 2。
返回执行最少操作次数，使得 nums 包含一个子序列，该子序列的元素和等于 target。如果无法获得这样的子序列，返回 -1。
子序列是可以通过删除某些或不删除元素而不改变其余元素顺序，从另一个数组派生出来的数组。
示例 1：
输入：nums = [1,2,8], target = 7
输出：1
解释：在第一次操作中，我们选择元素 nums[2]。数组变为 nums = [1,2,4,4]。
此时，nums 包含子序列 [1,2,4]，其和为 7。
可以证明没有更短的操作序列能得到和为 7 的子序列。
示例 2：
输入：nums = [1,32,1,2], target = 12
输出：2
解释：在第一次操作中，我们选择元素 nums[1]。数组变为 nums = [1,1,2,16,16]。
在第二次操作中，我们选择元素 nums[3]。数组变为 nums = [1,1,2,16,8,8]
此时，nums 包含子序列 [1,1,2,8]，其和为 12。
可以证明没有更短的操作序列能得到和为 12 的子序列。
示例 3：
输入：nums = [1,32,1], target = 35
输出：-1
解释：可以证明没有操作序列能得到和为 35 的子序列。
约束条件：
1 <= nums.length <= 10001 <= nums[i] <= 2^30nums仅由非负的 2 的幂组成1 <= target < 2^31
解题思路
这是一道关于位操作和贪心策略的问题。核心思想是将问题分解为对 target 的每一位进行处理。
算法思路：
可行性检查：如果数组所有元素的和小于
target，直接返回 -1按位处理：从
target的最低位开始，逐位处理每个设置位（值为 1 的位）贪心策略：对于
target的每个设置位bit：- 计算所有小于等于
2^bit的数的总和sum - 如果
sum >= 2^bit，说明可以直接组成这一位，贪心地选择尽可能大的数 - 如果
sum < 2^bit，需要找到最小的大于2^bit的数进行分解
- 计算所有小于等于
分解操作：当需要分解时，选择最小的大于当前位值的数，将其分解为两个较小的数，操作次数加 1
关键观察：
- 由于所有数都是 2 的幂，可以用位操作高效处理
- 贪心选择总是最优的：优先使用大的数可以减少总的分解次数
- 每次分解都会产生两个相同的较小数，这保证了分解的有效性
这种方法的时间复杂度是 O(n log max(nums))，空间复杂度是 O(log max(nums))。
代码实现
class Solution {
public:
int minOperations(vector<int>& nums, int target) {
long long total = 0;
map<int, int> count;
for (int num : nums) {
total += num;
count[num]++;
}
if (total < target) return -1;
int operations = 0;
for (int bit = 0; bit < 31; bit++) {
if (!(target & (1 << bit))) continue;
int needed = 1 << bit;
long long available = 0;
for (auto& [val, cnt] : count) {
if (val <= needed) {
available += (long long)val * cnt;
}
}
if (available >= needed) {
// Greedily use the largest values first
int remaining = needed;
for (auto it = count.rbegin(); it != count.rend() && remaining > 0; ++it) {
int val = it->first;
int cnt = it->second;
if (val <= needed) {
int use = min(remaining / val, cnt);
remaining -= use * val;
count[val] -= use;
}
}
} else {
// Need to split a larger value
auto it = count.upper_bound(needed);
while (it != count.end() && it->second == 0) {
++it;
}
int val = it->first;
count[val]--;
count[val / 2] += 2;
operations++;
bit--; // Retry this bit
}
}
return operations;
}
};
class Solution:
def minOperations(self, nums: List[int], target: int) -> int:
from collections import defaultdict
total = sum(nums)
if total < target:
return -1
count = defaultdict(int)
for num in nums:
count[num] += 1
operations = 0
bit = 0
while bit < 31:
if not (target & (1 << bit)):
bit += 1
continue
needed = 1 << bit
available = 0
for val, cnt in count.items():
if val <= needed:
available += val * cnt
if available >= needed:
# Greedily use the largest values first
remaining = needed
for val in sorted(count.keys(), reverse=True):
if val <= needed and remaining > 0:
use = min(remaining // val, count[val])
remaining -= use * val
count[val] -= use
bit += 1
else:
# Need to split a larger value
larger_vals = [val for val in count.keys() if val > needed and count[val] > 0]
val = min(larger_vals)
count[val] -= 1
count[val // 2] += 2
operations += 1
return operations
public class Solution {
public int MinOperations(IList<int> nums, int target) {
long total = 0;
var count = new Dictionary<int, int>();
foreach (int num in nums) {
total += num;
if (count.ContainsKey(num)) {
count[num]++;
} else {
count[num] = 1;
}
}
if (total < target) return -1;
int operations = 0;
int bit = 0;
while (bit < 31) {
if ((target & (1 << bit)) == 0) {
bit++;
continue;
}
int needed = 1 << bit;
long available = 0;
foreach (var kvp in count) {
if (kvp.Key <= needed) {
available += (long)kvp.Key * kvp.Value;
}
}
if (available >= needed) {
// Greedily use the largest values first
int remaining = needed;
var sortedKeys = count.Keys.OrderByDescending(x => x).ToList();
foreach (int val in sortedKeys) {
if (val <= needed && remaining > 0) {
int use = Math.Min(remaining / val, count[val]);
remaining -= use * val;
count[val] -= use;
}
}
bit++;
} else {
// Need to split a larger value
int minLarger = int.MaxValue;
foreach (var kvp in count) {
if (kvp.Key > needed && kvp.Value > 0) {
minLarger = Math.Min(minLarger, kvp.Key);
}
}
count[minLarger]--;
if (count.ContainsKey(minLarger / 2)) {
count[minLarger / 2] += 2;
} else {
count[minLarger / 2] = 2;
}
operations++;
}
}
return operations;
}
}
var minOperations = function(nums, target) {
let total = nums.reduce((sum, num) => sum + num, 0);
if (total < target) return -1;
const count = new Map();
for (const num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
let operations = 0;
let bit = 0;
while (bit < 31) {
if (!(target & (1 << bit))) {
bit++;
continue;
}
const needed = 1 << bit;
let available = 0;
for (const [val, cnt] of count) {
if (val <= needed) {
available += val * cnt;
}
}
if (available >= needed) {
// Greedily use the largest values first
let remaining = needed;
const sortedKeys = Array.from(count.keys()).sort((a, b) => b - a);
for (const val of sortedKeys) {
if (val <= needed && remaining > 0) {
const use = Math.min(Math.floor(remaining / val), count.get(val));
remaining -= use * val;
count.set(val, count.get(val) - use);
}
}
bit++;
} else {
// Need to split a larger value
let minLarger = Infinity;
for (const [val, cnt] of count) {
if (val > needed && cnt > 0) {
minLarger = Math.min(minLarger, val);
}
}
count.set(minLarger, count.get(minLarger) - 1);
count.set(minLarger / 2, (count.get(minLarger / 2) || 0) + 2);
operations++;
}
}
return operations;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log max(nums)) | 需要处理最多 log max(nums) 位，每位需要遍历数组 |
| 空间复杂度 | O(log max(nums)) | 存储不同 2 的幂的计数器 |