题目描述
给你一个下标从 0 开始的整数数组 nums
和一个整数 k
。
一次操作中,你可以选择 nums
中满足 0 <= i < nums.length - 1
的一个下标 i
,并将 nums[i]
和 nums[i + 1]
替换为数字 nums[i] & nums[i + 1]
,其中 &
表示按位 AND
操作。
请你返回 至多 k
次操作以内,使 nums
中所有剩余元素按位 OR
结果的 最小值。
样例
输入:nums = [3,5,3,2,7], k = 2
输出:3
解释:执行以下操作:
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]),得到 nums 为 [1,3,2,7]。
2. 将 nums[2] 和 nums[3] 替换为 (nums[2] & nums[3]),得到 nums 为 [1,3,2]。
最终数组的按位或值为 3 。
3 是 k 次操作以内,可以得到的剩余元素的最小按位或值。
输入:nums = [7,3,15,14,2,8], k = 4
输出:2
解释:执行以下操作:
1. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]),得到 nums 为 [3,15,14,2,8]。
2. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]),得到 nums 为 [3,14,2,8]。
3. 将 nums[0] 和 nums[1] 替换为 (nums[0] & nums[1]),得到 nums 为 [2,2,8]。
4. 将 nums[1] 和 nums[2] 替换为 (nums[1] & nums[2]),得到 nums 为 [2,0]。
最终数组的按位或值为 2 。
2 是 k 次操作以内,可以得到的剩余元素的最小按位或值。
输入:nums = [10,7,10,3,9,14,9,4], k = 1
输出:15
解释:不执行任何操作,nums 的按位或值为 15。
15 是 k 次操作以内,可以得到的剩余元素的最小按位或值。
限制
1 <= nums.length <= 10^5
0 <= nums[i] < 2^30
0 <= k < nums.length
算法
(思维题) $O(n \log m)$
- 从最高位到最低位,逐位考虑这一位上是否能在 $k$ 步操作之内把 $1$ 都消除掉。
- 需要考虑高位的操作对低位的影响,所以在考虑某一位时,需要把可以被消除的高位也考虑进来,即设置一个掩码 $mask$,当这一位的 $1$ 可以被消除时,将这一位设置为 $1$。
- 考虑这一位时,先将这一位的 $mask$ 设置为 $1$,设置一个变量 $m$,初始时为 $mask$。然后从左到右遍历每个数字,首先让 $m$ 和当前的数字 $x$ 按位
AND
,如果 $m$ 大于 $0$,则说明这个数字 $x$ 需要被替换,则替换次数加 $1$。否则,$m$ 重置为 $mask$,表示一段合并的区间已经结束。 - 如果最终替换的次数大于 $k$,则将 $mask$ 这一位置为 $0$,表示考虑后面低位时,不受到这一位的影响。
- 最终答案为 $mask$ 取反。
时间复杂度
- 每个数字被遍历 $\log m$ 次,其中 $m$ 是最大可能的数字,故总时间复杂度为 $O(n \log m)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minOrAfterOperations(vector<int>& nums, int k) {
const int n = nums.size();
int mask = 0;
for (int i = 29; i >= 0; i--) {
mask |= 1 << i;
int m = mask, tot = 0;
for (int x : nums) {
m &= x;
if (m > 0) ++tot;
else m = mask;
}
if (tot > k)
mask ^= 1 << i;
}
return mask ^ ((1 << 30) - 1);
}
};