56-数组中出现一次的数字

2020-05-07  本文已影响0人  一方乌鸦

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

重点 xorNumber & (xorNumber - 1) 去掉右边第一位1
xorNumber ^ (xorNumber & (xorNumber - 1)) 找到 xorNumber 右边第一位 1,用以分组

class Solution {
    public int[] singleNumbers(int[] nums) {
        int xorNumber = nums[0];
        for(int k=1; k<nums.length; k++){
            xorNumber ^=nums[k];
        }
        int onePosition = xorNumber ^ (xorNumber & (xorNumber - 1)) ;
        int ans1 = 0, ans2 = 0;
        for(int i=0; i<nums.length; i++){
            if((nums[i]&onePosition)==0){
                ans1^=nums[i];
            }else{
                ans2^=nums[i];
            }
        }
        
        return new int[] {ans1, ans2};
    }
}
上一篇 下一篇

猜你喜欢

热点阅读