2025-01-08：找到按位或最接近 K 的子数组。用go语言，给定一个数组 nums 和一个整数 k，你的目标是找到一个子数
【摘要】 2025-01-08：找到按位或最接近 K 的子数组。用go语言，给定一个数组 nums 和一个整数 k，你的目标是找到一个子数组，使得该子数组中所有元素进行按位或运算后的结果与 k 之间的绝对差值尽量小。具体地，你需要确定一个子数组 nums[l…r]，使得以下表达式的值最小化：|k - (nums[l] OR nums[l + 1] … OR nums[r])|最后，返回这个最小绝对差值...
2025-01-08：找到按位或最接近 K 的子数组。用go语言，给定一个数组 nums 和一个整数 k，你的目标是找到一个子数组，使得该子数组中所有元素进行按位或运算后的结果与 k 之间的绝对差值尽量小。
具体地，你需要确定一个子数组 nums[l…r]，使得以下表达式的值最小化：
|k - (nums[l] OR nums[l + 1] … OR nums[r])|
最后，返回这个最小绝对差值。
这里所说的子数组指的是数组中连续的非空元素序列。
1 <= nums.length <= 100000。
1 <= nums[i] <= 1000000000。
1 <= k <= 1000000000。
输入：nums = [1,2,4,5], k = 3。
输出：0。
解释：
子数组 nums[0…1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。
答案2025-01-08：
题目来自leetcode3171。
大体步骤如下：
1.初始化 bitsMaxPos 数组，用于记录每个元素在每位上的最大位置，初始值为 -1。
2.初始化结果 res 为整数最大值 math.MaxInt。
3.遍历数组 nums：
a. 对于每个元素，记录其在 bitsMaxPos 数组中每位上的位置，即进行按位运算并更新 bitsMaxPos。
b. 构建二维数组 posToBit，记录每个位的最大位置和该位的值。
c. 按照每位最大位置倒序排序 posToBit 数组。
d. 遍历 posToBit 数组，计算包含当前位的所有可能组合的按位或值，更新结果 res。
4.最终返回 res 作为最小绝对差值。
总体而言，这个算法的时间复杂度取决于数组长度 n，其中对数组进行了遍历和排序操作。
额外空间复杂度主要取决于辅助数组的大小和额外变量的空间开销，约为 O(n)。
Go完整代码如下：
package main
import (
"fmt"
"sort"
"math"
)
func minimumDifference(nums []int, k int) int {
n := len(nums)
bitsMaxPos := make([]int, 31)
for i := range bitsMaxPos {
bitsMaxPos[i] = -1
}
res := math.MaxInt
for i := 0; i < n; i++ {
for j := 0; j <= 30; j++ {
if nums[i]>>j & 1 == 1 {
bitsMaxPos[j] = i
}
}
posToBit := make([][2]int, 0)
for j := 0; j <= 30; j++ {
if bitsMaxPos[j] != -1 {
posToBit = append(posToBit, [2]int{bitsMaxPos[j], j})
}
}
sort.Slice(posToBit, func(a, b int) bool {
return posToBit[a][0] > posToBit[b][0]
})
val := 0
for j, p := 0, 0; j < len(posToBit); p = j {
for j < len(posToBit) && posToBit[j][0] == posToBit[p][0] {
val |= 1 << posToBit[j][1]
j++
}
res = min(res, int(math.Abs(float64(val - k))))
}
}
return res
}
func main() {
nums := []int{1,2,4,5}
k := 3
result := minimumDifference(nums,k)
fmt.Println(result)
}
Rust完整代码如下：
use std::cmp;
use std::collections::HashSet;
fn minimum_difference(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut bits_max_pos = [-1; 31];
let mut res = i32::MAX;
for i in 0..n {
for j in 0..=30 {
if nums[i] >> j & 1 == 1 {
bits_max_pos[j] = i as i32;
}
}
let mut pos_to_bit: Vec<(i32, i32)> = Vec::new();
for j in 0..=30 {
if bits_max_pos[j] != -1 {
pos_to_bit.push((bits_max_pos[j], j as i32));
}
}
pos_to_bit.sort_by(|a, b| b.0.cmp(&a.0));
let mut val = 0;
let mut j = 0;
let mut p = 0;
while j < pos_to_bit.len() {
p = j;
while j < pos_to_bit.len() && pos_to_bit[j].0 == pos_to_bit[p].0 {
val |= 1 << pos_to_bit[j].1;
j += 1;
}
res = cmp::min(res, (val - k).abs() as i32);
}
}
res
}
fn main() {
let nums = vec![1, 2, 4, 5];
let k = 3;
let result = minimum_difference(nums, k);
println!("{}", result);
}
C完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// Helper function to find the minimum of two integers
int min(int a, int b) {
return (a < b) ? a : b;
}
int minimumDifference(int nums[], int size, int k) {
int bitsMaxPos[31];
for (int i = 0; i < 31; i++) {
bitsMaxPos[i] = -1;
}
int res = INT_MAX;
for (int i = 0; i < size; i++) {
for (int j = 0; j <= 30; j++) {
if ((nums[i] >> j) & 1 == 1) {
bitsMaxPos[j] = i;
}
}
int posToBit[size][2];
int count = 0;
for (int j = 0; j <= 30; j++) {
if (bitsMaxPos[j] != -1) {
posToBit[count][0] = bitsMaxPos[j];
posToBit[count][1] = j;
count++;
}
}
// Sort
for (int a = 0; a < count; a++) {
for (int b = a+1; b < count; b++) {
if (posToBit[a][0] < posToBit[b][0]) {
int temp0 = posToBit[a][0];
int temp1 = posToBit[a][1];
posToBit[a][0] = posToBit[b][0];
posToBit[a][1] = posToBit[b][1];
posToBit[b][0] = temp0;
posToBit[b][1] = temp1;
}
}
}
int val = 0;
for (int j = 0, p = 0; j < count; p = j) {
while (j < count && posToBit[j][0] == posToBit[p][0]) {
val |= 1 << posToBit[j][1];
j++;
}
res = min(res, abs(val - k));
}
}
return res;
}
int main() {
int nums[] = {1, 2, 4, 5};
int size = sizeof(nums) / sizeof(nums[0]);
int k = 3;
int result = minimumDifference(nums, size, k);
printf("%d\n", result);
return 0;
}
C++完整代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
int min(int a, int b) {
return (a < b) ? a : b;
}
int minimumDifference(std::vector<int> nums, int k) {
int n = nums.size();
std::vector<int> bitsMaxPos(31, -1);
int res = INT_MAX;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= 30; j++) {
if ((nums[i] >> j) & 1 == 1) {
bitsMaxPos[j] = i;
}
}
std::vector<std::pair<int, int>> posToBit;
for (int j = 0; j <= 30; j++) {
if (bitsMaxPos[j] != -1) {
posToBit.push_back(std::make_pair(bitsMaxPos[j], j));
}
}
std::sort(posToBit.begin(), posToBit.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.first > b.first;
});
int val = 0;
for (int j = 0, p = 0; j < posToBit.size(); p = j) {
while (j < posToBit.size() && posToBit[j].first == posToBit[p].first) {
val |= 1 << posToBit[j].second;
j++;
}
res = min(res, std::abs(val - k));
}
}
return res;
}
int main() {
std::vector<int> nums = {1, 2, 4, 5};
int k = 3;
int result = minimumDifference(nums, k);
std::cout << result << std::endl;
return 0;
}
Python完整代码如下：
# -*-coding:utf-8-*-
import math
def minimum_difference(nums, k):
n = len(nums)
bits_max_pos = [-1] * 31
res = math.inf
for i in range(n):
for j in range(31):
if nums[i] >> j & 1 == 1:
bits_max_pos[j] = i
pos_to_bit = []
for j in range(31):
if bits_max_pos[j] != -1:
pos_to_bit.append((bits_max_pos[j], j))
pos_to_bit.sort(key=lambda x: x[0], reverse=True)
val = 0
j = 0
p = 0
while j < len(pos_to_bit):
p = j
while j < len(pos_to_bit) and pos_to_bit[j][0] == pos_to_bit[p][0]:
val |= 1 << pos_to_bit[j][1]
j += 1
res = min(res, abs(val - k))
return res
if __name__ == "__main__":
nums = [1, 2, 4, 5]
k = 3
result = minimum_difference(nums, k)
print(result)
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）