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)
