2024-10-30：或值至少 K 的最短子数组 I。用go语言，给定一个非负整数数组 nums 和一个整数 k，我们需要判断数

福大大架构师每日一题

发布于 2024-10-31 17:33:31

15100

代码可运行

运行总次数：0

代码可运行

2024-10-30：或值至少 K 的最短子数组 I。用go语言，给定一个非负整数数组 nums 和一个整数 k，我们需要判断数组中是否存在一个最短的非空子数组，使得该子数组所有元素的按位或（OR）运算结果至少为 k。如果找到了这样的子数组，返回其长度；如果不存在，则返回 -1。

输入：nums = [1,2,3], k = 2。

输出：1。

解释：

子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

注意，[2] 也是一个特别子数组。

答案2024-10-30：

chatgpt

题目来自leetcode3095。

大体步骤如下：

代码逻辑分析

1.初始化：

• minLen 被设置为 math.MaxInt32，用于存储找到的最短子数组的长度。
• n 是数组 nums 的长度。

2.解决方案 1：

• 对于每一个索引 i 从 0 到 n-1，表示当前子数组的结束位置。
• 对于每一个 j 从 i 递减到 0，表示当前子数组的起始位置。
• 检查从 j 到 i 这段子数组的按位或结果，调用 isSpecial 函数。
• 如果返回的结果满足大于等于 k，则更新 minLen 为当前子数组长度 i-j+1 的最小值。
• 最后，如果没有找到满足条件的子数组，返回 -1；否则返回 minLen。

3.isSpecial 函数：

• 接受数组 nums 和子数组的起始、结束索引 j、i，以及目标值 k。
• 初始化结果 res 为 0。
• 遍历子数组，计算位或结果 res |= nums[idx]。
• 最后返回一个布尔值，判断 res 是否大于等于 k。

4.解决方案 2：

• 该方法做了优化，先检查当前元素 nums[i] 是否已经大于等于 k，如果是，则直接返回 1，因为单独的元素就满足了条件。
• 同样遍历 j，更新 nums[j] 为 nums[j] | nums[i]。并检查是否满足按位或条件。
• 如果找到了满足条件的子数组，则更新 minLen。
• 最后根据 minLen 的最终值返回结果。

时间复杂度

• 解决方案 1：最坏情况下，外层循环和内层循环都是进行 O(n^2) 的遍历。
• 解决方案 2：外层循环为 O(n)，内层循环的最坏情况下为 O(n)，因此在某些情况下也可能达到 O(n^2) 的复杂度。
• 最终时间复杂度：最坏情况为 O(n^2)。

空间复杂度

• 两种解决方案都只使用了常量级的额外空间，主要是用于存储变量 minLen 和中间结果 res，以及输入数组 nums 本身。没有使用额外的数据结构来增加空间开销。
• 最终空间复杂度：O(1)。

总结

代码通过两种方式实现了目标，虽然最坏情况下时间复杂度达到 O(n^2) 但在实际操作中，尤其是对于较小的输入数组，可能表现良好。空间复杂度保持在常数级别，确保了算法的高效性。

Go完整代码如下：

package main

import(
"fmt"
"math"
)

func minimumSubarrayLength(nums []int, k int)int{
    minLen := math.MaxInt32
    n :=len(nums)

// 解决方案 1 的实现
for i :=0; i < n; i++{
for j := i; j >=0; j--{
if isSpecial(nums, j, i, k){
                minLen = min(minLen, i-j+1)
}
}
}

if minLen == math.MaxInt32{
return-1
}
return minLen
}

func isSpecial(nums []int, j int, i int, k int)bool{
    res :=0
for idx := j; idx <= i; idx++{
        res |= nums[idx]
}
return res >= k
}

func min(a, b int)int{
if a < b {
return a
}
return b
}

// 解决方案 2 的实现
func minimumSubarrayLengthOptimized(nums []int, k int)int{
    minLen := math.MaxInt32
    n :=len(nums)

for i :=0; i < n; i++{
if nums[i]>= k {
return1
}
for j := i -1; j >=0&&(nums[i]|nums[j])!= nums[j]; j--{
            nums[j]|= nums[i]
if nums[j]>= k {
                minLen = min(minLen, i-j+1)
}
}
}

if minLen == math.MaxInt32{
return-1
}
return minLen
}
func main(){
    nums :=[]int{1,2,3}
    k :=2
    fmt.Println(minimumSubarrayLength(nums, k))
    fmt.Println(minimumSubarrayLengthOptimized(nums, k))
}

Rust完整代码如下：

use std::cmp;

fnminimum_subarray_length(nums:Vec<i32>, k:i32)->i32{
letmut min_len= i32::MAX;
letn= nums.len();

// 解决方案 1 的实现
foriin0..n {
forjin(0..=i).rev(){
ifis_special(&nums, j, i, k){
                min_len = cmp::min(min_len,(i - j +1)asi32);
}
}
}

if min_len == i32::MAX {
-1
}else{
        min_len
}
}

fnis_special(nums:&Vec<i32>, j:usize, i:usize, k:i32)->bool{
letmut res=0;
foridxin j..=i {
        res |= nums[idx];
}
    res >= k
}

fnminimum_subarray_length_optimized(nums:Vec<i32>, k:i32)->i32{
letmut min_len= i32::MAX;
letmut nums= nums.clone();// 复制一份 nums

letn= nums.len();

foriin0..n {
if nums[i]>= k {
return1;
}
forjin(0..i).rev(){
if(nums[i]| nums[j])!= nums[j]{
                nums[j]|= nums[i];
if nums[j]>= k {
                    min_len = cmp::min(min_len,(i - j +1)asi32);
}
}else{
break;// 提高效率，如果不再变化，则可直接跳出
}
}
}

if min_len == i32::MAX {
-1
}else{
        min_len
}
}

fnmain(){
letnums=vec![1,2,3];
letk=2;

println!("{}",minimum_subarray_length(nums.clone(), k));// 解决方案 1
println!("{}",minimum_subarray_length_optimized(nums, k));// 解决方案 2
}