2024-10-30：或值至少 K 的最短子数组 I。用 go 语言，给定一个非负整数数组 nums 和一个整数 k，我们需要判断数组中是否存在一个最短的非空子数组，使得该子数组所有元素的按位或（OR）运

2024-10-30
北京
本文字数：2295 字
阅读完需：约 8 分钟

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 {      return 1    }    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;
fn minimum_subarray_length(nums: Vec<i32>, k: i32) -> i32 {    let mut min_len = i32::MAX;    let n = nums.len();
    // 解决方案 1 的实现    for i in 0..n {        for j in (0..=i).rev() {            if is_special(&nums, j, i, k) {                min_len = cmp::min(min_len, (i - j + 1) as i32);            }        }    }
    if min_len == i32::MAX {        -1    } else {        min_len    }}
fn is_special(nums: &Vec<i32>, j: usize, i: usize, k: i32) -> bool {    let mut res = 0;    for idx in j..=i {        res |= nums[idx];    }    res >= k}
fn minimum_subarray_length_optimized(nums: Vec<i32>, k: i32) -> i32 {    let mut min_len = i32::MAX;    let mut nums = nums.clone(); // 复制一份 nums
    let n = nums.len();
    for i in 0..n {        if nums[i] >= k {            return 1;        }        for j in (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) as i32);                }            } else {                break; // 提高效率，如果不再变化，则可直接跳出            }        }    }
    if min_len == i32::MAX {        -1    } else {        min_len    }}
fn main() {    let nums = vec![1, 2, 3];    let k = 2;
    println!("{}", minimum_subarray_length(nums.clone(), k));          // 解决方案 1    println!("{}", minimum_subarray_length_optimized(nums, k));      // 解决方案 2}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/01890d278fa7a3695faf1d45e】。

福大大架构师每日一题

关注

公众号：福大大架构师每日一题 2021-02-15 加入

公众号：福大大架构师每日一题

发布

暂无评论

创作场景