找出唯一成對的數 1-1000這一千個數放在含有1001個元素的陣列中，只有唯一的一個元素值重復，其他均只出現一次，每個陣列元素只能訪問一次，設計一個演算法，將它找出來；不用輔助存盤空間，能否設計一個演算法實作？
思路一、
解題思路：由于每個元素只能訪問一次，所以不能使用雙重for回圈暴力求解，不能使用輔助空間所以也不能使用木桶排序的思想，所以我們采用位運算中的異或運算求解 基礎知識A^0=A A^A=0
int x = 0;
for (int i = 1; i <= arr.length-1; i++) {
x = (x ^ i);
}
for (int i = 0; i < arr.length; i++) {
x = x ^ arr[i];
}
System.out.println(x);
第一個for回圈將陣列中的元素以^的形式排列起來
arr=[1,2,3,2,4]
//第一個for回圈結束后x等價于0^1^2^3^2^4
第二個for回圈相當于把x中相同的數字消去 且每個數字只消去一次 最終只留下多余的一個數
//0^1^2^3^2^4^1 == 0^2^3^2^4
//0^1^2^3^2^4^2 == 0^3^2^4
//0^1^2^3^2^4^3 == 0^2^4
//0^1^2^3^2^4^4 == 0^2 ==2
思路二、
使用一個額外的相同大小的陣列計數，以原陣列的陣列元素作為額外陣列的下標，沒當原陣列內元素出現，額外的陣列下標對應的元素加1 最后查看額外陣列中哪個元素為2 輸出下標即為成對數
for (int i = 0; i < arr.length; i++) {
help[arr[i]]++;
}
for (int i = 0; i < arr.length; i++) {
if (help[i] == 2) {
System.out.println(i);
break;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/165391.html
標籤：其他
上一篇：并查集