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：

chatgpt^[1]

题目来自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完整代码如下：

packagemain

import(
"fmt"
"sort"
"math"
)

funcminimumDifference(nums[]int,kint)int{
n:=len(nums)
bitsMaxPos:=make([]int,31)
fori:=rangebitsMaxPos{
bitsMaxPos[i]=-1
}

res:=math.MaxInt
fori:=0;i<n;i++{
forj:=0;j<=30;j++{
ifnums[i]>>j&1==1{
bitsMaxPos[j]=i
}
}

posToBit:=make([][2]int,0)
forj:=0;j<=30;j++{
ifbitsMaxPos[j]!=-1{
posToBit=append(posToBit,[2]int{bitsMaxPos[j],j})
}
}
sort.Slice(posToBit,func(a,bint)bool{
returnposToBit[a][0]>posToBit[b][0]
})

val:=0
forj,p:=0,0;j<len(posToBit);p=j{
forj<len(posToBit)&&posToBit[j][0]==posToBit[p][0]{
val|=1<<posToBit[j][1]
j++
}
res=min(res,int(math.Abs(float64(val-k))))
}
}
returnres
}



funcmain(){
nums:=[]int{1,2,4,5}
k:=3
result:=minimumDifference(nums,k)
fmt.Println(result)
}

Rust完整代码如下：

usestd::cmp;
usestd::collections::HashSet;

fnminimum_difference(nums:Vec<i32>,k:i32)->i32{
letn=nums.len();
letmutbits_max_pos=[-1;31];

letmutres=i32::MAX;
foriin0..n{
forjin0..=30{
ifnums[i]>>j&1==1{
bits_max_pos[j]=iasi32;
}
}

letmutpos_to_bit:Vec<(i32,i32)>=Vec::new();
forjin0..=30{
ifbits_max_pos[j]!=-1{
pos_to_bit.push((bits_max_pos[j],jasi32));
}
}

pos_to_bit.sort_by(|a,b|b.0.cmp(&a.0));

letmutval=0;
letmutj=0;
letmutp=0;

whilej<pos_to_bit.len(){
p=j;
whilej<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()asi32);
}
}
res
}

fnmain(){
letnums=vec![1,2,4,5];
letk=3;
letresult=minimum_difference(nums,k);
println!("{}",result);
}

C完整代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

//Helperfunctiontofindtheminimumoftwointegers
intmin(inta,intb){
return(a<b)?a:b;
}

intminimumDifference(intnums[],intsize,intk){
intbitsMaxPos[31];
for(inti=0;i<31;i++){
bitsMaxPos[i]=-1;
}

intres=INT_MAX;
for(inti=0;i<size;i++){
for(intj=0;j<=30;j++){
if((nums[i]>>j)&1==1){
bitsMaxPos[j]=i;
}
}

intposToBit[size][2];
intcount=0;
for(intj=0;j<=30;j++){
if(bitsMaxPos[j]!=-1){
posToBit[count][0]=bitsMaxPos[j];
posToBit[count][1]=j;
count++;
}
}

//Sort
for(inta=0;a<count;a++){
for(intb=a+1;b<count;b++){
if(posToBit[a][0]<posToBit[b][0]){
inttemp0=posToBit[a][0];
inttemp1=posToBit[a][1];
posToBit[a][0]=posToBit[b][0];
posToBit[a][1]=posToBit[b][1];
posToBit[b][0]=temp0;
posToBit[b][1]=temp1;
}
}
}

intval=0;
for(intj=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));
}
}
returnres;
}

intmain(){
intnums[]={1,2,4,5};
intsize=sizeof(nums)/sizeof(nums[0]);
intk=3;
intresult=minimumDifference(nums,size,k);
printf("%d\n",result);
return0;
}

C++完整代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>

intmin(inta,intb){
return(a<b)?a:b;
}

intminimumDifference(std::vector<int>nums,intk){
intn=nums.size();
std::vector<int>bitsMaxPos(31,-1);

intres=INT_MAX;
for(inti=0;i<n;i++){
for(intj=0;j<=30;j++){
if((nums[i]>>j)&1==1){
bitsMaxPos[j]=i;
}
}

std::vector<std::pair<int,int>>posToBit;
for(intj=0;j<=30;j++){
if(bitsMaxPos[j]!=-1){
posToBit.push_back(std::make_pair(bitsMaxPos[j],j));
}
}
std::sort(posToBit.begin(),posToBit.end(),[](conststd::pair<int,int>&a,conststd::pair<int,int>&b){
returna.first>b.first;
});

intval=0;
for(intj=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));
}
}
returnres;
}

intmain(){
std::vector<int>nums={1,2,4,5};
intk=3;
intresult=minimumDifference(nums,k);
std::cout<<result<<std::endl;
return0;
}

Python完整代码如下：

#-*-coding:utf-8-*-

importmath

defminimum_difference(nums,k):
n=len(nums)
bits_max_pos=[-1]*31

res=math.inf
foriinrange(n):
forjinrange(31):
ifnums[i]>>j&1==1:
bits_max_pos[j]=i

pos_to_bit=[]
forjinrange(31):
ifbits_max_pos[j]!=-1:
pos_to_bit.append((bits_max_pos[j],j))

pos_to_bit.sort(key=lambdax:x[0],reverse=True)

val=0
j=0
p=0
whilej<len(pos_to_bit):
p=j
whilej<len(pos_to_bit)andpos_to_bit[j][0]==pos_to_bit[p][0]:
val|=1<<pos_to_bit[j][1]
j+=1
res=min(res,abs(val-k))

returnres

if__name__=="__main__":
nums=[1,2,4,5]
k=3
result=minimum_difference(nums,k)
print(result)

引用链接

[1]chatgpt:https://chatbotsplace.com/?rc=nnNWSCJ7EP