JZ56 数组中只出现一次的两个数字

https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=13&tags=&title=&difficulty=0&judgeStatus=0&rp=0

解题思路:

  1. 遍历异或,把那些出现两次的消掉。剩下的就是x,y的异或
  2. 找出x,y中不同的数字,在二进制中就是两个数字的异或是1
  3. 重新遍历数组,将他们按照那一位是否是1进行分组,分组再异或,得到的就是x, y
    public int[] FindNumsAppearOnce (int[] array) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : array)
            n ^= num;
        while((n & m) == 0)
            m <<= 1;
        for(int num : array){
            if((num & m) != 0) x ^= num;
            else y ^= num;
        }
        if(x >= y) return new int[] {y, x};
        else return new int[] {x, y};
    }
上一篇:Web1 命令执行(三)


下一篇:初见 | 数据结构 | ODT