题目描述
给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。
请你返回 最小 的绝对差值。
子数组 是数组中连续的 非空 元素序列。
示例 1：
输入：nums = [1,2,4,5], k = 3
输出：0
解释：
子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。
示例 2：
输入：nums = [1,3,1,3], k = 2
输出：1
解释：
子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。
示例 3：
输入：nums = [1], k = 10
输出：9
解释：
只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 109
解法
方法一：双指针 + 位运算
根据题目描述，我们需要求出数组 $\textit{nums}$ 下标 $l$ 到 $r$ 的元素的按位或运算的结果，即 $\textit{nums}[l] \lor \textit{nums}[l + 1] \lor \cdots \lor \textit{nums}[r]$。其中 $\lor$ 表示按位或运算。
如果我们每次固定右端点 $r$，那么左端点 $l$ 的范围是 $[0, r]$。每次移动右端点 $r$，按位或的结果只会变大，我们用一个变量 $s$ 记录当前的按位或的结果，如果 $s$ 大于 $k$，我们就将左端点 $l$ 向右移动，直到 $s$ 小于等于 $k$。在移动左端点 $l$ 的过程中，我们需要维护一个数组 $cnt$，记录当前区间内每个二进制位上 $0$ 的个数，当 $cnt[h]$ 为 $0$ 时，说明当前区间内的元素在第 $h$ 位上都为 $0$，我们就可以将 $s$ 的第 $h$ 位设置为 $0$。
时间复杂度 $O(n \times \log M)$，空间复杂度 $O(\log M)$。其中 $n$ 和 $M$ 分别是数组 $\textit{nums}$ 的长度和数组 $\textit{nums}$ 中元素的最大值。
相似题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
m = max(nums).bit_length()
cnt = [0] * m
s = i = 0
ans = inf
for j, x in enumerate(nums):
s |= x
ans = min(ans, abs(s - k))
for h in range(m):
if x >> h & 1:
cnt[h] += 1
while i < j and s > k:
y = nums[i]
for h in range(m):
if y >> h & 1:
cnt[h] -= 1
if cnt[h] == 0:
s ^= 1 << h
i += 1
ans = min(ans, abs(s - k))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public int minimumDifference(int[] nums, int k) {
int mx = 0;
for (int x : nums) {
mx = Math.max(mx, x);
}
int m = 32 - Integer.numberOfLeadingZeros(mx);
int[] cnt = new int[m];
int n = nums.length;
int ans = Integer.MAX_VALUE;
for (int i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
ans = Math.min(ans, Math.abs(s - k));
for (int h = 0; h < m; ++h) {
if ((nums[j] >> h & 1) == 1) {
++cnt[h];
}
}
while (i < j && s > k) {
for (int h = 0; h < m; ++h) {
if ((nums[i] >> h & 1) == 1 && --cnt[h] == 0) {
s ^= 1 << h;
}
}
++i;
ans = Math.min(ans, Math.abs(s - k));
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int mx = *max_element(nums.begin(), nums.end());
int m = 32 - __builtin_clz(mx);
int n = nums.size();
int ans = INT_MAX;
vector<int> cnt(m);
for (int i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
ans = min(ans, abs(s - k));
for (int h = 0; h < m; ++h) {
if (nums[j] >> h & 1) {
++cnt[h];
}
}
while (i < j && s > k) {
for (int h = 0; h < m; ++h) {
if (nums[i] >> h & 1 && --cnt[h] == 0) {
s ^= 1 << h;
}
}
ans = min(ans, abs(s - k));
++i;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | func minimumDifference(nums []int, k int) int {
m := bits.Len(uint(slices.Max(nums)))
cnt := make([]int, m)
ans := math.MaxInt32
s, i := 0, 0
for j, x := range nums {
s |= x
ans = min(ans, abs(s-k))
for h := 0; h < m; h++ {
if x>>h&1 == 1 {
cnt[h]++
}
}
for i < j && s > k {
y := nums[i]
for h := 0; h < m; h++ {
if y>>h&1 == 1 {
cnt[h]--
if cnt[h] == 0 {
s ^= 1 << h
}
}
}
ans = min(ans, abs(s-k))
i++
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | function minimumDifference(nums: number[], k: number): number {
const m = Math.max(...nums).toString(2).length;
const n = nums.length;
const cnt: number[] = Array(m).fill(0);
let ans = Infinity;
for (let i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
ans = Math.min(ans, Math.abs(s - k));
for (let h = 0; h < m; ++h) {
if ((nums[j] >> h) & 1) {
++cnt[h];
}
}
while (i < j && s > k) {
for (let h = 0; h < m; ++h) {
if ((nums[i] >> h) & 1 && --cnt[h] === 0) {
s ^= 1 << h;
}
}
ans = Math.min(ans, Math.abs(s - k));
++i;
}
}
return ans;
}
|
方法二：哈希表 + 枚举
根据题目描述，我们需要求出数组 $nums$ 下标 $l$ 到 $r$ 的元素的按位或运算的结果，即 $nums[l] \lor nums[l + 1] \lor \cdots \lor nums[r]$。其中 $\lor$ 表示按位或运算。
如果我们每次固定右端点 $r$，那么左端点 $l$ 的范围是 $[0, r]$。由于按位或之和随着 $l$ 的减小而单调递增，并且 $\textit{nums}[i]$ 的值不超过 $10^9$，因此区间 $[0, r]$ 最多只有 $30$ 种不同的值。因此，我们可以用一个集合来维护所有的 $nums[l] \lor nums[l + 1] \lor \cdots \lor nums[r]$ 的值。当我们从 $r$ 遍历到 $r+1$ 时，以 $r+1$ 为右端点的值，就是集合中每个值与 $nums[r + 1]$ 进行按位或运算得到的值，再加上 $nums[r + 1]$ 本身。因此，我们只需要枚举集合中的每个值，与 $nums[r]$ 进行按位或运算，就可以得到以 $r$ 为右端点的所有值，将每个值与 $k$ 相减后取绝对值，就可以得到以 $r$ 为右端点的所有值与 $k$ 的差的绝对值，其中的最小值就是答案。
时间复杂度 $O(n \times \log M)$，空间复杂度 $O(\log M)$。其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度和数组 $nums$ 中的最大值。
相似题目：
| class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
ans = inf
s = set()
for x in nums:
s = {x | y for y in s} | {x}
ans = min(ans, min(abs(y - k) for y in s))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public int minimumDifference(int[] nums, int k) {
int ans = Integer.MAX_VALUE;
Set<Integer> pre = new HashSet<>();
for (int x : nums) {
Set<Integer> cur = new HashSet<>();
for (int y : pre) {
cur.add(x | y);
}
cur.add(x);
for (int y : cur) {
ans = Math.min(ans, Math.abs(y - k));
}
pre = cur;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int ans = INT_MAX;
unordered_set<int> pre;
for (int x : nums) {
unordered_set<int> cur;
cur.insert(x);
for (int y : pre) {
cur.insert(x | y);
}
for (int y : cur) {
ans = min(ans, abs(y - k));
}
pre = move(cur);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | func minimumDifference(nums []int, k int) int {
ans := math.MaxInt32
pre := map[int]bool{}
for _, x := range nums {
cur := map[int]bool{x: true}
for y := range pre {
cur[x|y] = true
}
for y := range cur {
ans = min(ans, max(y-k, k-y))
}
pre = cur
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function minimumDifference(nums: number[], k: number): number {
let ans = Infinity;
let pre = new Set<number>();
for (const x of nums) {
const cur = new Set<number>();
cur.add(x);
for (const y of pre) {
cur.add(x | y);
}
for (const y of cur) {
ans = Math.min(ans, Math.abs(y - k));
}
pre = cur;
}
return ans;
}
|