XOR找到重複陣列中的

我已經看到了在這個線程這個問題的解決方案 - >How to find a duplicate element in an array of shuffled consecutive integers?XOR找到重複陣列中的

但我現在遇到的問題是它基本不變。

int arr[10] = {1,2,3,4,5,6,7,8,4,9}; 
    int a= 0; 
    for(int i=0;i<10;i++) { 
    a= a^ arr[i] ^i; 
    } 
    cout<<a;

考慮上面提到的代碼片段。事情工作正常。但是，當我添加一個0到上面提到的數組，如int arr[11] = {0,1,2,3,4,5,6,7,8,4,9};我沒有得到正確的重複元素。有人能糾正我在這裏犯的錯嗎？

來源

2011-11-05 Ajai

你忘記改變for循環？ '我<11'而不是'我<10'？ CS中最棘手的兩個問題：命名事件，緩存失效以及逐個錯誤。 –

不，我做了改變。 – Ajai

技巧依賴於值介於1和n之間。如果數字在其他一些範圍內，則必須抵消它們。

static const int n = 11; 
int arr[n] = {0,1,2,3,4,5,6,7,8,4,9}; 
int offset = 1; 
int a= 0; 
for(int i=0;i<n;i++) { 
a= a^ (arr[i]+offset) ^i; 
} 
cout<< (a-offset);

來源

2011-11-05 04:13:12

對不起，我只是驗證了這一點與其他幾個輸入，我認爲解決方案需要改變一點點。如果元素被排序，這段代碼可以正常工作。如果他們不是？它不適用於以下輸入， \t int arr [20] = {0,1,10,3,2,4,5,7,6,8,11,9,15,12,13 ，4,16,18,17,14}; \t int offset = 1; \t int a = 0;對於（int i = 0; i <20; i ++）{ \t a = a ^（arr [i] + offset）^ i; \t} \t cout <<（a-offset）; – Ajai

你的數組的大小是20，但你有我<11。 –

對於這樣的錯誤我非常抱歉。是的你的解決方案工作正常 – Ajai

我猜它可能有一個事實，即I值會則是一樣的編曲做的[I]

這就是像做：

00000001^00000001

這等於00000000

我可能會錯誤地思考，但不會這樣搞砸這個過程嗎？

來源

2011-11-05 04:04:54 DanZimm

是的，我注意到它，我甚至在每次迭代時手動記下輸出，而數組中的0是唯一讓這個問題看起來很奇怪的東西。我不確定使用什麼值，以便該方法不會破壞實際的數組。 – Ajai

我想我明白髮生了什麼事。您可能已將循環更改爲

for(int i=0; i<11; i++) 
    ...

因爲您向循環中添加了一個額外的元素。問題在於它不是與10異或，這不是數組中的數字。所以，該算法停止工作。

int arr[11] = {0,1,2,3,4,5,6,7,8,4,9}; 
int a= 0; 
for(int i=0;i<10;i++) { 
    a= a^ arr[i] ^i; 
} 
a = a^arr[10]; 

cout<<a;

現在，它的異或NUMS從0到9的兩倍（相當於零）和4個額外的時間，所以結果應該是4

來源

2011-11-05 04:13:44

再次如上所述，這對於排序的數組工作正常。 – Ajai

XOR找到重複陣列中的

回答

相關問題