Medium

题目描述

给定一个整数数组 arr，返回所有非空子数组的按位或运算结果的不同值的数量。

子数组的按位或是子数组中每个整数按位或运算的结果。只有一个整数的子数组的按位或就是该整数本身。

子数组是数组中元素的连续非空序列。

示例 1：

输入：arr = [0]
输出：1
解释：只有一个可能的结果：0。

示例 2：

输入：arr = [1,1,2]
输出：3
解释：可能的子数组为 [1], [1], [2], [1, 1], [1, 2], [1, 1, 2]。
这些结果为 1, 1, 2, 1, 3, 3。
共有 3 个不同的值，所以答案是 3。

示例 3：

输入：arr = [1,2,4]
输出：6
解释：可能的结果为 1, 2, 3, 4, 6, 和 7。

提示：

  • 1 <= arr.length <= 5 * 10^4
  • 0 <= arr[i] <= 10^9

解题思路

这道题需要计算所有子数组按位或运算的不同结果数量。

核心思路：

  1. 暴力方法会超时，我们需要利用按位或运算的性质进行优化
  2. 关键观察：对于以位置 i 结尾的所有子数组，它们的按位或结果数量是有限的
  3. 按位或运算具有单调性：a | b >= max(a, b)，且 a | b 的二进制位只会增加不会减少

优化策略：

  • 维护一个集合 dp，表示以当前位置结尾的所有子数组的按位或结果
  • 对于新的元素 arr[i]，新的结果集合为：{arr[i]} ∪ {x | arr[i] : x ∈ dp}
  • 由于按位或的性质，这个集合的大小不会超过 32（因为最多32个二进制位）

算法步骤：

  1. 使用动态规划，dp 存储以当前位置结尾的所有可能的按位或结果
  2. 对于每个新元素，计算它与之前所有结果的按位或，加上它本身
  3. 将所有结果加入总的结果集合中
  4. 返回结果集合的大小

时间复杂度优化到 O(32n)，因为每个位置最多产生32种不同的按位或结果。

代码实现

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> result;
        unordered_set<int> dp;
        
        for (int num : arr) {
            unordered_set<int> newDp;
            newDp.insert(num);
            
            for (int x : dp) {
                newDp.insert(x | num);
            }
            
            dp = newDp;
            result.insert(dp.begin(), dp.end());
        }
        
        return result.size();
    }
};

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        result = set()
        dp = set()
        
        for num in arr:
            dp = {num} | {x | num for x in dp}
            result |= dp
            
        return len(result)

public class Solution {
    public int SubarrayBitwiseORs(int[] arr) {
        HashSet<int> result = new HashSet<int>();
        HashSet<int> dp = new HashSet<int>();
        
        foreach (int num in arr) {
            HashSet<int> newDp = new HashSet<int>();
            newDp.Add(num);
            
            foreach (int x in dp) {
                newDp.Add(x | num);
            }
            
            dp = newDp;
            foreach (int val in dp) {
                result.Add(val);
            }
        }
        
        return result.Count;
    }
}

var subarrayBitwiseORs = function(arr) {
    const result = new Set();
    let dp = new Set();
    
    for (const num of arr) {
        const newDp = new Set();
        newDp.add(num);
        
        for (const x of dp) {
            newDp.add(x | num);
        }
        
        dp = newDp;
        for (const val of dp) {
            result.add(val);
        }
    }
    
    return result.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(32n)
空间复杂度O(32n)

其中 n 是数组长度。由于按位或运算的性质，每个位置最多产生 32 种不同的结果（对应 32 个二进制位），因此时间和空间复杂度都是线性的。

相关题目