二維位數組的最大或值

假設有一個二維數組位(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

二維位數組的最大或值

回答

相關問題