給定一個由 n 個整陣列成的陣列，所有數字都是唯一的，其中一個除外。
如果 n 是偶數，則重復數重復 n/2 次
如果 n 是奇數，則重復數重復 (n-1)/2 或 (n 1)/2 次
重復數在陣列中與自身不相鄰
撰寫一個程式來在不使用額外空間的情況下找到重復的數字。
這就是我試圖解決問題的方式。
如果 n 是偶數，則有 n/2 個重復元素。此外，重復元素不應相鄰。因此，如果說有 6 個元素，則重復 3 個元素。元素可以在索引 0,2 和 4 或 1,3 和 5 處。因此，如果我只檢查是否有任何元素在索引 0 和 2 處重復，然后在索引 1 和 3 處，我可以獲得重復元素。
如果 n 是奇數，則有 2 個選擇。
如果 (n 1)/2 個元素是重復的，那么我們可以只檢查索引 0 和 2。例如說有 7 個元素，其中 4 個是重復的，那么重復元素必須位于索引 0,2,4 和6.
但是，當 n 為奇數時，我找不到找到 (n-1)/2 重復元素的方法。我想過使用 xor 和 sums 但找不到方法。
uj5u.com熱心網友回復：
讓我們將重復的元素稱為“多數”。
Boyer-Moore 多數投票演算法可以在這里提供幫助。如果存在任何此類元素，則該演算法會找到一個元素，該元素在輸入的一半以上元素中重復出現。
但就你而言，情況很有趣。大多數情況可能不會超過一半的次數。除了重復的一個和重復的數字不相鄰之外，所有元素都是唯一的。此外，多數元素肯定存在。
所以，
- 對陣列中偶數索引處的數字運行多數投票演算法。再次遍歷輸入陣列以驗證演算法報告的元素確實是多數。
- 如果在上面的步驟中我們沒有得到多數元素，您可以對陣列中奇數索引的數字重復上述程序。您可以更巧妙地執行此第二步，因為我們確定存在多數元素。因此，任何重復的數字都會是結果。
在上面的實作中，有一個很好的小優化空間。
我想我不應該在這里解釋多數投票演算法。如果你想讓我知道，請告訴我。顯然，在不知道這個多數演算法的情況下，我們應該能夠用一些計數邏輯來做到這一點（這很可能最終與多數演算法相同）。但僅僅因為它是一個標準演算法，我們就可以利用它。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/382604.html
上一篇：計算所有已排序陣列組合的平均值