題目

整數數組 sockets 記錄了一個襪子禮盒的顏色分布情況，其中 sockets[i] 表示該襪子的顏色編號。禮盒中除了一款撞色搭配的襪子，每種顏色的襪子均有兩只。請設計一個程序，在時間復雜度 O(n)，空間復雜度O(1) 內找到這雙撞色搭配襪子的兩個顏色編號。

示例 1：

輸入：sockets = [4, 5, 2, 4, 6, 6]
輸出：[2,5] 或 [5,2]

示例 2：

輸入：sockets = [1, 2, 4, 1, 4, 3, 12, 3]
輸出：[2,12] 或 [12,2]

提示：

2 <= sockets.length <= 10000

代碼

class Solution {
public int[] sockCollocation(int[] nums) {
int z = 0;
for(int i = 0;i < nums.length; i++){
z = z ^ nums[i];
}

    int m = 1;while((m & z) == 0){m = m << 1;}int x = 0, y = 0;for(int i = 0;i < nums.length; i++){if((nums[i] & m) == 0){//結果為 0 的子數組，一邊統計用異或統計xx = x ^ nums[i];} else {//結果為 1 的子數組，一邊統計用異或統計yy = y ^ nums[i];}}return new int[]{x, y};
}

}