运算

发表于 更新于 分类于 阅读次数：

只出现一次的数字[🔥49]

思路：

利用异或运算^

1. a^a =0
2. a^0=a

然后运算满足交换率

即

a^b^a=a^a^b

最后就可以得出 b是单身狗

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int singleNumber(int[] nums) {
        int x = 0;
        System.out.println(12^1);
        for (int num : nums){
            // 1. 遍历 nums 执行异或运算
            x ^= num;
            System.out.println(x);

        }  
        return x;            // 2. 返回出现一次的数字 x
    }
}

变种：字节后端，变成有序数组，需要O(logN)复杂度。 思路：二分查找，如果nums[mid]出现了两次，则左边或右边肯定有一边剩余了奇数个数字，朝奇数个的方向走。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == nums[mid ^ 1]) {
                l = mid + 1; // 单身狗在右边
            } else {
                r = mid;     // 单身狗在左边或就是mid
            }
        }
        return nums[l];
    }
}

![](/images/3617fe7504c0cae01de7b87b4d19720a.png)

寻找重复数[34]

1

汉明距离

思路：

  1. 调用函数 Integer.bitCount(x) 统计x中 为1的个数
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int hammingDistance(int x, int y) {
        //bitCount 用于统计 二进制中 1的数量
        // x ^ y特性：x和y相同 则x ^ y为0，x = 0 或者 y = 0 则x ^ y = 非0数
        System.out.println(0 ^ 6); // 6
        System.out.println(1 ^ 6); // 无规则
        // 001
        // 110
        // 111 = 7
        System.out.println(6 ^ 6); // 0
        return Integer.bitCount(x ^ y);
    }
}