所以我有一個問題，我有一個整數陣列，首先我將一個區間定義為一個好的區間 iff，在區間內每個整數出現偶數（包括零）次。我想在給定的整數陣列中找到好的間隔數。例如，如果array = [7, 7, 1, 5, 5, 1]，那么好的區間是[1, 2], [3, 6], [4, 5], [1, 6] 對應于連續子陣列 [7, 7], [1, 5, 5, 1], [5, 5], [7, 7, 1, 5, 5, 1]。如果 array = [4, 5, 6, 5, 4]，則沒有好的區間。
我有一個天真的解決方案，即使用 2 個回圈并檢查每個可能的間隔是否有一個好的間隔，但這需要 O(n^2) 時間。我想找到一個在 O(nlogn) 時間內運行的更好的解決方案，我覺得使用散列可能會給我一個更快的解決方案，問題是我不知道如何將它合并到我的答案中。我一直在閱讀滾動 robin-karp 散列演算法來給我一些想法，但我認為這個演算法不適用于我所尋求的。你們對使用散列在 O(nlogn) 時間內解決這個問題的演算法有什么想法嗎？
uj5u.com熱心網友回復：
假設您的陣列稱為 A。
對于每個索引 i，您可以計算 A[:i] 中出現奇數次的元素集。現在您的問題相當于找到所有 i, j 使得這些集合相等。
在最壞的情況下，這仍然是 O(n^2)，但是您可以使用集合的散列而不是使用集合。為了提高效率，散列需要從前一組的散列中增量計算。一種這樣的方法是使用集合元素的（通用散列函式）的 XOR。有了這個，您可以在 O(1) 中從哈希中添加和洗掉單個元素，并且它的好處是添加和洗掉元素是完全相同的操作，非常適合這個問題，其中奇偶校驗而不是奇偶校驗元素的準確計數很重要。
所以為索引 0 到 n 計算這個新陣列：
B[0] = 0
B[i 1] = HASH(A[i]) XOR B[i]
然后計算所有 0<=i<j<=n 使得 B[i]=B[j] （您可以在 O(n) 時間內完成，例如使用常規地圖）。
這是一個概率正確的演算法，因為如果你不走運，非空集的哈希值可能為零。如果您使用通用 b 位哈希，則正確概率的上限約為 exp(-n2/2^(b 1)) - 從生日問題概率獲得。因此，如果您使用 128 位哈希，那么對于您在實踐中可能找到的任何輸入都是非常安全的。
例如，這里的 Python 代碼實作了使用集合并在最壞情況下以 O(n^2) 運行的樸素版本。
import collections
def naive_evens(A):
B = frozenset()
counts = collections.Counter()
counts[B] = 1
total = 0
for a in A:
B = B.symmetric_difference({a})
total = counts[B]
counts[B] = 1
return total
這是使用散列并在 O(n) 時間內運行的概率正確版本。它HASH用作通用哈希（帶有隨機種子HA）和引數HW，HM用于描述要創建的哈希的字長和位數。為了避免 0 到 0 的散列，陣列元素被修改，使它們都是正數（通過向每個元素添加一些東西，使最小元素始終為 1）。
import collections
import random
HW = 256
HM = 128
HA = random.randrange(1 << HW)
def HASH(x):
h = (HA * x) % (1 << HW)
return h >> (HW - HM)
def smart_evens(A):
B = 0
counts = collections.Counter()
counts[B] = 1
total = 0
M = min(A)
for x in A:
B = B ^ HASH(x - M 1)
total = counts[B]
counts[B] = 1
return total
uj5u.com熱心網友回復：
運行時間：O(n * r)，其中 n 是輸入陣列的大小，r 是不同元素的數量。在最壞的情況下，r 接近于 n，這是 O(n^2)。
假設：您的整數是連續的或至少很小。如果您的整數遠大于不同整數的數量，您應該使用哈希為每個整數賦予唯一的 id：0、1、2、...，并將我的演算法應用于這些 id。
初始化以下內容：
bitvec = 0。我們將使用它來跟蹤我們在決議輸入陣列時看到每個元素的次數的奇偶校驗。
bitvec_to_count：每個新鍵的起始值為零的哈希，并將跟蹤我們看到每個 bitvec 的次數。
設定 bitvec_to_count[0] = 1。我們用它來表示我們已經見過一次不代表任何元素的 bitvec。
現在決議陣列。對于陣列的第 i 個元素，翻轉位向量的第 i 個位（因為該元素的奇偶校驗已更改）。增加此位向量的計數。
最后，對 bitvec_to_count 哈希中的所有計數（值）取 choose(count, 2) 的總和。這是你的答案。
這利用了這樣一個事實，即良好的間隔正是那些元素的奇偶校驗在開始之前和結束時相同的那些（因為間隔本身的元素的奇偶校驗都是零，因為它們都顯示為偶數次）。
這是作業的 Ruby 代碼；應該很容易翻譯成 Python。
def f(arr)
bitvec = 0
bitvec_to_count = Hash.new{|h, k| h[k] = 0}
bitvec_to_count[bitvec] = 1
arr.each do |val|
bitvec ^= 1 << val
bitvec_to_count[bitvec] = 1
end
ans = 0
bitvec_to_count.values.each do |count|
ans = count * (count - 1) / 2
end
return ans
end
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/523895.html
標籤：算法哈希间隔
上一篇：演算法改進：計算航向的有符號變化
下一篇：片段大小與TabLayout重疊