我有一個n正整數數組。我想計算一個大小k為 modulo的所有連續子陣列乘積的列表p。例如對於以下數組：
a = [3, 12, 5, 2, 3, 7, 4, 3]
同k = 3和p = 12，所有的有序列表k尺度的連續子陣列產品將是：
k_products = [180, 120, 30, 42, 84, 84]
和模p我們有：
k_products_p = [0, 0, 6, 6, 0, 0]
我們可以k_products使用滑動窗口輕鬆計算。我們所要做的就是計算第一個k大小的子數組的乘積，然後k_product使用以下公式計算下一個元素：
k_product[i] = k_product[i - 1] * a[i + k] / a[i - 1]
在形成整個列表後，我們可以計算k_product[i] % p每個i得到k_product_p。就是這樣。O(n)複雜度還不錯。
但是如果 的元素a[i]很大， k_product 的元素可能會溢出，因此我們無法計算k_product_p。另外，例如，我們不能執行以下操作：
k_product[i] = ((k_product[i - 1] % p) * (a[i + k] % p) / (a[i - 1] % p)) % p // incorrect
那麼有沒有一種快速的算法來做到這一點？請注意，p不一定是素數，也不一定是 的元素的互質數a。
編輯：如評論中所述，python 中不會溢出，但處理非常大的數字將非常耗時。
這不是滑動窗口算法，但它是在 O(n) 時間內解決此問題的一種簡單有效的方法，無需任何除法：
讓 A 成為您的原始數組。我們將想像在 A 的每個第 k 個元素上都有一個“標記”——元素 A[0]、A[k]、A[2k] 等。這確保了 A 中的每個 k 長度的窗口將恰好包含一個標記。
現在，創建兩個新數組 B 和 C，使得：
在數組 B 中，每個元素 B[i] 將包含 A[i] 和所有後續元素的乘積（mod p），直到但不包括下一個標記。如果 A[i] 被標記，則 B[i] = 1。您可以從 i=n-1 到 i=0 一次反向計算。
在數組 C 中，每個元素 C[i] 將包含 A[i] 和所有前面的元素的乘積（mod p），直到並包括前一個標記。如果標記了 A[i]，則 C[i] = A[i]。您可以在從 i=0 到 i=n-1 的單次傳遞中進行計算。
現在，您可以輕鬆地在恆定時間內計算任何 k 長度窗口的完整乘積，因為來自 A[i]...A[i+k-1] 的任何窗口的乘積只是B[i] * C[ i+k-1]。請記住，窗口內只有一個標記。B[i]是標記前元素的乘積，C[i+k-1]是被標記元素與其後元素的乘積。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句