0898-子数组按位或操作
我们有一个非负整数数组 arr
。
对于每个(连续的)子数组 sub = [arr[i], arr[i + 1], ..., arr[j]]
( i <= j
),我们对 sub
中的每个元素进行按位或操作,获得结果 arr[i] | arr[i + 1] | ... | arr[j]
。
返回可能结果的数量。 多次出现的结果在最终答案中仅计算一次。
示例 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:
**输入:** arr = [1,2,4]
**输出:** 6
**解释:**
可能的结果是 1,2,3,4,6,以及 7 。
提示:
1 <= nums.length <= 5 * 104
0 <= nums[i] <= 109
方法一:集合
分析
显然,最简单的方法就是枚举所有满足 i <= j
的 (i, j)
,并计算出不同的 result(i, j) = A[i] | A[i + 1] | ... | A[j]
的数量。由于 result(i, j + 1) = result(i, j) | A[j + 1]
,因此我们可以在 O(N^2) 的时间复杂度计算出所有的 result(i, j)
,其中 N 是数组 A
的长度。
我们尝试优化一下这种最简单的枚举方法。可以发现,对于固定的 j
,result(j, j), result(j - 1, j), result(j - 2), j, ..., result(1, j)
的值是单调不降的,因为将 result(k, j)
对 A[k - 1]
做按位或操作,得到的结果 result(k - 1, j)
一定不会变小。并且,根据按位或操作的性质,如果把 result(k, j)
和 result(k - 1, j)
都用二进制表示,那么后者将前者二进制表示中的若干个 0
变成了 1
。
由于数组 A
中都是小于 10^9
的正整数,它们的二进制表示最多只有 32
位。因此从 result(j, j)
开始到 result(1, j)
结束,最多只会有 32
个 0
变成了 1
,也就是说,result(j, j), result(j - 1, j), result(j - 2), j, ..., result(1, j)
中最多只有 32
个不同的数。这样我们就可以维护一个集合,存储所有以 j
为结尾的 result
值。当结尾从 j
枚举到 j + 1
时,我们将集合中的每个数对 A[j + 1]
做按位或操作,得到的新的 result
值也不会超过 32
个。
算法
我们用一个集合 cur
存储以 j
为结尾的 result
值,即所有满足 i <= j
的 A[i] | ... | A[j]
的值。集合的大小不会超过 32
。
1 | class Solution { |
1 | class Solution(object): |
复杂度分析
时间复杂度:O(N \log W),其中 N 是数组
A
的长度,W 是A
中最大的数。空间复杂度:O(N \log W)。在给出的代码中用集合
ans
存放了所有答案,会使用 O(N \log W) 的空间。但这题只要返回答案的数量,因此可以只用一个变量对集合cur
的大小进行累加,这样空间复杂度可以降低为 O(\log W)。