或值至少为 K 的最短子数组 II

100271. 或值至少为 K 的最短子数组 II

给你一个非负整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值至少为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

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

输出：1

解释：

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

示例 2：

输入：nums = [2,1,8], k = 10

输出：3

解释：

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

示例 3：

输入：nums = [1,2], k = 0

输出：1

解释：

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

提示：

1 <= nums.length <= 2 * 10⁵
0 <= nums[i] <= 10⁹
0 <= k <= 10⁹

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minimumSubarrayLength(vector<int>& nums, int k) { } };

golang 解法, 执行用时: 84 ms, 内存消耗: 11.8 MB, 提交时间: 2024-03-31 21:42:42

func minimumSubarrayLength(nums []int, k int) int {
	ans := math.MaxInt
	type pair struct{ or, left int }
	ors := []pair{} // 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)
	for i, x := range nums {
		ors = append(ors, pair{0, i})
		j := 0
		for idx := range ors {
			p := &ors[idx]
			p.or |= x
			if p.or >= k {
				ans = min(ans, i-p.left+1)
			}
			if ors[j].or == p.or {
				ors[j].left = p.left // 原地去重：合并相同值，左端点取靠右的
			} else {
				j++
				ors[j] = *p
			}
		}
		ors = ors[:j+1] // 去重：移除多余元素
	}
	if ans == math.MaxInt {
		return -1
	}
	return ans
}

func minimumSubarrayLength2(nums []int, k int) int {
	ans := math.MaxInt
	type pair struct{ or, left int }
	ors := []pair{} // 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)
	for i, x := range nums {
		ors = append(ors, pair{0, i})
		ors[0].or |= x
		j := 0
		for _, p := range ors[1:] {
			p.or |= x
			if ors[j].or == p.or {
				ors[j].left = p.left // 原地去重：合并相同值，左端点取靠右的
			} else {
				j++
				ors[j] = p
			}
		}
		ors = ors[:j+1] // 去重：移除多余元素
		for len(ors) > 0 && ors[0].or >= k {
			ans = min(ans, i-ors[0].left+1)
			ors = ors[1:]
		}
	}
	if ans == math.MaxInt {
		return -1
	}
	return ans
}

cpp 解法, 执行用时: 116 ms, 内存消耗: 85.4 MB, 提交时间: 2024-03-31 21:41:44

class Solution {
public:
    int minimumSubarrayLength(vector<int> &nums, int k) {
        int ans = INT_MAX;
        vector<pair<int, int>> ors; // 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)
        for (int i = 0; i < nums.size(); i++) {
            ors.emplace_back(0, i);
            int j = 0;
            for (auto &p : ors) {
                auto &[or_, left] = p;
                or_ |= nums[i];
                if (or_ >= k) {
                    ans = min(ans, i - left + 1);
                }
                if (ors[j].first == or_) {
                    ors[j].second = left; // 原地去重：合并相同值，左端点取靠右的
                } else {
                    ors[++j] = p;
                }
            }
            ors.resize(j + 1); // 去重：移除多余元素
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

java 解法, 执行用时: 61 ms, 内存消耗: 69.3 MB, 提交时间: 2024-03-31 21:41:10

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        List<int[]> ors = new ArrayList<>(); // 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)
        for (int i = 0; i < nums.length; i++) {
            ors.add(new int[]{0, i});
            int j = 0;
            for (int[] or : ors) {
                or[0] |= nums[i];
                if (or[0] >= k) {
                    ans = Math.min(ans, i - or[1] + 1);
                }
                if (ors.get(j)[0] == or[0]) {
                    ors.get(j)[1] = or[1]; // 原地去重：合并相同值，左端点取靠右的
                } else {
                    ors.set(++j, or);
                }
            }
            ors.subList(j + 1, ors.size()).clear(); // 去重：移除多余元素
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public int minimumSubarrayLength2(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        int[][] ors = new int[32][2]; // 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)
        int m = 0;
        for (int i = 0; i < nums.length; i++) {
            ors[m][0] = 0;
            ors[m++][1] = i;
            int j = 0;
            for (int idx = 0; idx < m; idx++) {
                ors[idx][0] |= nums[i];
                if (ors[idx][0] >= k) {
                    ans = Math.min(ans, i - ors[idx][1] + 1);
                }
                if (ors[j][0] != ors[idx][0]) {
                    ors[++j][0] = ors[idx][0];
                }
                ors[j][1] = ors[idx][1];
            }
            m = j + 1; // 去重：移除多余元素
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

python3 解法, 执行用时: 516 ms, 内存消耗: 34.9 MB, 提交时间: 2024-03-31 21:40:03

class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
        ans = inf
        d = dict()  # key 是右端点为 i 的子数组 OR, value 是该子数组左端点的最大值
        for i, x in enumerate(nums):
            d = {or_ | x: left for or_, left in d.items()}
            d[x] = i  # 只包含 x 的子数组
            for or_, left in d.items():
                if or_ >= k:
                    ans = min(ans, i - left + 1)
        return ans if ans < inf else -1

    def minimumSubarrayLength2(self, nums: List[int], k: int) -> int:
        ans = inf
        ors = []  # 保存 (右端点为 i 的子数组 OR, 该子数组左端点的最大值)
        for i, x in enumerate(nums):
            ors.append([0, i])
            j = 0
            for p in ors:
                p[0] |= x
                if p[0] >= k:
                    ans = min(ans, i - p[1] + 1)
                if ors[j][0] == p[0]:
                    ors[j][1] = p[1]  # 原地去重：合并相同值，左端点取靠右的
                else:
                    j += 1
                    ors[j] = p
            del ors[j + 1:]  # 去重：移除多余元素
        return ans if ans < inf else -1

上一题

下一题

详情