在數組中總結數字

假設我有一個N個非負整數的數組，每個數都可以非常大（0-> 100,000）。我們還假設N可能非常大（〜100,000,000）。在數組中總結數字

對於數組[a0 a1 ... aN-1]，我想寫一個函數，它返回整個數組的（-2）^ ai之和。我想有O（n * log（n））時間複雜度和O（n）空間。

例如，取[1 2 3] - 這將返回（-2）^ 1 +（-2）^ 2 +（-2）^ 3 = -6 另一個限制是對於超過100,000,000 ，函數應該返回-1;

甲幼稚（但錯誤的）的解決方案是以下內容：

int solve(vector<int> &A) { 
     int answer = 0; 
     for (auto iter = A.begin(); iter != A.end(); ++iter) { 
     answer += pow(-2, *iter); 
     } 
     return (answer <= 1e8) ? answer : -1; 
    }

這不起作用B/C應答會溢出爲值> 31（假設天然符號整數大小爲4個字節）。對於數組中的值大於63的情況，使用long也不起作用。

我能想到的一個高級解決方案是使用std :: sort對數組進行排序，然後進行排序。對於數組中大於31的值，我們從數組中的值中減去31的倍數。這是可接受的B/C，我們正在處理指數的總和。我很好奇是否有已知的O（n * log（n））複雜度，O（n）空間解決這個問題。

來源

2017-01-23 user1373317

*使用long也不起作用b/c在數組中的值大於63時會失效。* - 如果阻止您實現解決方案的唯一因素是這樣，那麼有些類允許任意大小的整數，例如[boost :: multiprecision]（http://www.boost.org/doc/libs/1_63_0/libs/multiprecision/doc/html/boost_multiprecision/intro.html）。 – PaulMcKenzie

請注意，(-2)^K具有不同的簡單二進制表示形式：它對於偶數K爲..00001000..，對於奇數K（2的補碼）爲..1111110000..。

所以，你可以創建數組（積分或布爾）積累在二進制表示的總和。它的長度應該通過數組中的最大值來確定（開銷取決於N - 大約是Log2（N）單元格）。

然後遍歷數組，並將當前數字的二進制表示添加到累加器。例如用於陣列A=[2,3,4]

value(K)  binary(-2)^K accum 
          00000000  
2   100   00000100 
3   11111000  11111100 
4   00010000  00001100

每個添加操作花費最大值（A）+ LOG2（N）基本OPS

可能的微型優化 - 排序輸入陣列和組重複的值。例如，如果array包含8的值4，則可以輕鬆地採用8*(-2)^4= 10000 << 3 = 10000000進行單班操作而無需7次添加操作。

來源

2017-01-23 06:37:46 MBo

這是一個很好的解決方案 - 它讓我不再看比特表示 – user1373317

一個想法......

你的功能回答2個問題：

1）是否導致適合在100M極限 2）什麼是項目超過100M

你再也較低的總和如果1）不滿足，則不得不計算後者，所以如果某物適合int或不適合，則最終計數可以不關心。

爲了使事情更容易，我們可以使用計數排序和總數。讓我們製作計數，它將保持2 ^（i）的乘數，所以最終的總和將是sum（counts [i] * 2^i）。不是計數不使用符號觸發器，我們必須在填充它時放置適當的符號。

現在我們可以減少計數陣列。請注意，如果計數[I]> 2，則總和將改性如下數組相同的：

計數[Ⅰ] -2
計數第[i + 1] 1

同樣適用於負號。因此，在從0到最大計數的一個循環中，我們可以減少計數值，每個值只剩下0和1/-1。

如您所知，2^N指數的值大於0..2^N-2值中至少2次累加的任何值的總和。因此，如果您的最高指數（減價後）大於28（2^28 = 268,435,456），則結果將不符合100,000,000。

現在，如果1）被佔用，你知道最後的和臨時的結果不會大於268,435,456，所以它將適合int類型，所以只需要做你的數學並再次檢查最終結果。

來源

2017-01-23 09:22:51

在數組中總結數字

回答

相關問題