子数组按位与的不同值

Question

子数组按位与的不同值

algorithm

3

如何找到数组所有子数组的按位与值的不同值数量。(数组大小<=1e5且数组元素<=1e6)。例如： A[]={1,2,3} 不同的值有4个(1,2,3,0)。

- Mr. Hilton

我已经尝试了很多，你能否详细说明一下？ - Mr. Hilton

2个回答

1

想象数字像列一样代表它们的位。我们将有水平延伸的1序列。例如:

Array index:  0  1  2  3  4  5  6  7

Bit columns:  0  1  1  1  1  1  0  0
              0  0  0  1  1  1  1  1
              0  0  1  1  1  1  1  0
              1  0  0  0  1  1  0  1
              0  1  1  1  1  1  1  0

向左看，任何在零之后进行and操作的子数组的位行将继续保持为零，这意味着该行在此之后不会发生任何变化。

以索引5为例。现在，从索引5到左侧排序1的水平序列将为我们提供一种检测位配置更改的简单方法（每次迭代都必须进行排序）：

                        Index 5 ->
Sorted bit rows:  1  0  0  0  1  1
                  0  0  0  1  1  1
                  0  0  1  1  1  1
                  0  1  1  1  1  1
                  0  1  1  1  1  1

  Index 5 to 4, no change
  Index 4 to 3, change
  Index 2 to 1, change
  Index 1 to 0, change

为了方便查看这些变化，克拉斯克维奇建议我们在进行操作时只记录每一行中最后一个未设置的位，从而指示1的水平序列的长度，并使用布尔数组（最多100万个数字）存储遇到的唯一位配置。

Numbers: 1,  2,  3

Bits:    1   0   1
         0   1   1

当我们从左到右移动时，记录每行最后一个未设置位的索引，并记录任何新的位配置（最多1e6个）：

Indexes of last unset bit for each row on each iteration
Numbers: 1,  2,  3

A[0]:   -1        arrayHash = [false,true,false,false], count = 1
         0

A[1]:   -1   1    Now sort the column descending, representing (current - index)
         0   0     the lengths of sequences of 1's extending to the left.

As we move from top to bottom on this column, each value change represents a bit
configuration and a possibly distinct count:

  Record present bit configuration b10
    => arrayHash = [false,true,true,false]

  1 => 1 - 1 => sequence length 0, ignore sequence length 0
  0 => 1 - 0 => sequence length 1,
                  unset second bit: b10 => b00 
                  => new bit configuration b00
                  => arrayHash = [true,true,true,false]

第三次迭代：

Numbers: 1,  2,  3

A[2]:   -1   1   1
         0   0   0

Record present bit configuration b11
    => arrayHash = [true,true,true,true]

由于我们不一定知道数组哈希已填满，因此我们继续执行。

  1 => 2 - 1 => sequence length 1
                  unset first bit: b11 => b10
                  => seen bit configuration b10
  0 => 2 - 0 => sequence length 2,
                  unset second bit: b10 => b00 
                  => seen bit configuration b00

- גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kraskevich · Accepted Answer

让我们将子数组的右边界 r 固定，想象左边界 l 从 r 开始向左移动。值得注意的是，当 and 的值发生改变时，它最多只能改变 O(log(MAX_VALUE)) 次。为什么这样说呢？因为当我们向左添加一个元素时，有两种情况：

子数组的 and 值不会发生改变。
子数组的 and 值会发生改变。此时，其位数会严格减少（因为它是前一个 and 值的子掩码）。

因此，我们只需要考虑那些使 and 值发生改变的 l 值。现在我们需要快速找到它们。

让我们从左往右遍历数组，并存储所有对于有效 i，最后一个元素不具有第 i 位的位置（我们可以通过迭代当前元素的所有位来更新它）。这样，我们就能够快速地找到下一个值发生更改的位置（也就是在所有已经设置了的位中，最大的位置）。如果我们对这些位置进行排序，我们就可以在 O(1) 的时间内找到下一个最大的位置。

该解决方案的总时间复杂度为 O(N * log(MAX_VALUE) * log(log(MAX_VALUE)))（我们需要迭代数组中每个元素的所有位，对于每个元素，我们都要对其位置数组进行排序并迭代它）。空间复杂度为 O(N + MAX_VALUE)。对于给定的约束条件，这应该已经足够好了。