class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
}
};
3171. 找到按位与最接近 K 的子数组
给你一个数组 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[2..3] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。
示例 2：
输入：nums = [1,2,1,2], 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相似题目
原站题解
rust 解法, 执行用时: 11 ms, 内存消耗: 3.7 MB, 提交时间: 2024-10-09 09:18:14
impl Solution {
pub fn minimum_difference(mut nums: Vec<i32>, k: i32) -> i32 {
let mut ans = i32::MAX;
let mut left = 0;
let mut bottom = 0;
let mut right_or = 0;
for right in 0..nums.len() {
right_or |= nums[right];
while left <= right && (nums[left] | right_or) > k {
ans = ans.min((nums[left] | right_or) - k);
if bottom <= left {
// 重新构建一个栈
// 由于 left 即将移出窗口，只需计算到 left+1
for i in (left + 1..right).rev() {
nums[i] |= nums[i + 1];
}
bottom = right;
right_or = 0;
}
left += 1;
}
if left <= right {
ans = ans.min(k - (nums[left] | right_or));
}
}
ans
}
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 62.1 MB, 提交时间: 2024-10-09 09:17:54
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minimumDifference = function(nums, k) {
let ans = Infinity, left = 0, bottom = 0, rightOr = 0;
for (let right = 0; right < nums.length; right++) {
rightOr |= nums[right];
while (left <= right && (nums[left] | rightOr) > k) {
ans = Math.min(ans, (nums[left] | rightOr) - k);
if (bottom <= left) {
// 重新构建一个栈
// 由于 left 即将移出窗口，只需计算到 left+1
for (let i = right - 1; i > left; i--) {
nums[i] |= nums[i + 1];
}
bottom = right;
rightOr = 0;
}
left++;
}
if (left <= right) {
ans = Math.min(ans, k - (nums[left] | rightOr));
}
}
return ans;
};
golang 解法, 执行用时: 84 ms, 内存消耗: 8 MB, 提交时间: 2024-06-10 00:10:58
func minimumDifference(nums []int, k int) int {
ans := math.MaxInt
for i, x := range nums {
ans = min(ans, abs(x-k))
for j := i - 1; j >= 0 && nums[j]|x != nums[j]; j-- {
nums[j] |= x
ans = min(ans, abs(nums[j]-k))
}
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
cpp 解法, 执行用时: 120 ms, 内存消耗: 92.4 MB, 提交时间: 2024-06-10 00:10:42
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int ans = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
ans = min(ans, abs(x - k));
for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
nums[j] |= x;
ans = min(ans, abs(nums[j] - k));
}
}
return ans;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 57 MB, 提交时间: 2024-06-10 00:10:29
class Solution {
public int minimumDifference(int[] nums, int k) {
int ans = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
ans = Math.min(ans, Math.abs(x - k));
for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
nums[j] |= x;
ans = Math.min(ans, Math.abs(nums[j] - k));
}
}
return ans;
}
}
python3 解法, 执行用时: 608 ms, 内存消耗: 30.8 MB, 提交时间: 2024-06-10 00:10:08
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
ans = inf
for i, x in enumerate(nums):
ans = min(ans, abs(x - k))
j = i - 1
while j >= 0 and nums[j] | x != nums[j]:
nums[j] |= x
ans = min(ans, abs(nums[j] - k))
j -= 1
return ans