二维位数组的最大或值

假设有一个二维数组位(m x n)位。二维位数组的最大或值

例如：

这里，m = 4，n = 5。

我可以翻转（0变成1,1变成0）任何行中的位。当你翻转特定行的位时，你翻转所有的位。

我的目标是获得给定的一对行之间的最大值OR。

也就是说，如果给定的对行的是(r1, r2)，那么我可以翻转任意数量的行r1和r2之间，我应该找到r1和r2之间的所有行的最大可能OR值。

在上面的例子中（考虑基于1的索引的数组），如果r1 = 1和r2 = 4，我可以翻转第一行得到。现在，如果我找到从1到4的所有行的值为OR，那么我会得到值31作为最大可能值OR值（可能有其他解决方案）。

而且，这将是很好的计算答案(r1, r1)，(r1, r1+1)，(r1, r1+2)，...，(r1, r2-1)在计算同为(r1,r2)。

约束

1 <= m x n <= 10^6

1 <= r1 <= r2 <= m

一个简单的蛮力解决方案将有一个O(2^m)时间复杂度。有更快的方法来计算这个吗？

来源

2017-07-22 Nikunj Madhogaria

这个算法的应用是什么？ – bcdan

我不明白你是如何来到O（2^m），如果你一点一点地执行操作，或者O（n^2），那么在行对上的天真迭代宁可是O（m * n^2）如果m <= sizeof（some_machine_integer），因为处理器会并行执行bit，否？ –

@ aka.nice由于有m行，我可以选择nC0，nC1，nC2，nC3，...，nCn行进行翻转。现在，nC0 + nC1 + nC2 + nC3 + ... + nCn = 2^n。 –

由于A <= A | B，一些A的价值只会上升，因为我们OR更多的号码A.

因此，我们可以使用二进制搜索。

我们可以使用函数来获取两行之间的最大值，并将第三行的结果保存为OR。然后比较这些第三行中的两个以获取更高级别的行，然后比较这些更高级别的行中的两个，依此类推，直到剩下一个。

使用你的例子：

array1 = 1 0 0 1 0 [0] 
     1 0 1 0 0 [1] 
     1 0 1 1 0 [2] 
     0 0 0 0 1 [3] 

array2 = 1 1 0 1 1 <-- [0] | ~[1] 
     1 1 1 1 0 <-- [2] | ~[3] 

array3 = 1 1 1 1 1 <-- [0] | [1]

而且很明显，你可以截断树枝时，根据需要m不是2

电源所以这将是O(m)时间。请记住，对于大量的行，可能不会有独特的解决方案。结果很可能是2^n - 1。

一个重要的优化：如果m >= n，那么输出必须是2^n - 1。假设我们有两个数字A和B.如果B有k数字缺失位，那么A或~A将被保证填充至少一个这些位。同样的道理，如果m >= log n，那么输出也必须是2^n - 1，因为每个A或~A保证填充B中至少一半的未填充位。

使用这些快捷方式，如果您愿意，可以使用蛮力搜索。我不是100％的二进制搜索算法在每一种情况下都有效。

来源

2017-07-22 15:08:11 bcdan

你如何决定'〜'哪一行？ –

只需检查所有四种组合。这可能是两个都需要'〜'。 – bcdan

考虑100行，在这种情况下，矩阵的上半部和下半部将会有2^50个组合。 –

考虑到翻转整个矩阵中的行然后将它们组合在一起以获得尽可能多的1的问题，我声称当列数小于2^m时这是可处理的，其中m是行数。考虑一行一行。在从0开始计数的阶段，你有不到2 ^（m-i）个零填充。由于翻转一行将0变为1，反之亦然，当前行或翻转的行将填充至少一半的零。当你完成所有的行时，你将有不到1个零填充，所以这个过程保证提供一个完美的答案。

我声称当列数至少为2^m时，这是可以处理的，其中m是行数。有2^m个可能的翻转行模式，但这只是O（N），其中N是列数。因此，在这种情况下，尝试所有可能的翻转行模式会为您提供O（N^2）算法。

来源

2017-07-23 10:57:29 mcdowella

二维位数组的最大或值

回答

相关问题