写在前面:

如果您觉得写得还可以,那就来关注在下的微信公众号吧“张氏文画”,不光有新鲜的 LeetCode 题解,还有经典的文章及短视频和大家分享,谢谢大家的关注!!!
qrcode_for_gh_671e52fa1e78_258.jpg

思路:

现在数组中有两个数字只出现1次,直接异或一次只能得到这两个数字的异或结果,但光从这个结果肯定无法得到这个两个数字。因此基于single number I 的思路——数组只能有一个数字出现1次

设题目中这两个只出现1次的数字分别为A和B,如果能将A,B分开到二个数组中,那显然符合“异或”解法的关键点了。因此这个题目的关键点就是将A,B分开到二个数组中。由于A,B肯定是不相等的,因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A,B分开到A组和B组。而这个数组中其它数字要么就属于A组,要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A,B了。而要判断A,B在哪一位上不相同,只要根据A异或B的结果就可以知道了,这个结果在二进制上为1的位就说明A,B在这一位上是不相同的。

比如

int a[] = {1, 1, 3, 5, 2, 2}

整个数组异或的结果为3^5,即 0x0011 ^ 0x0101 = 0x0110

对0x0110,第1位(由低向高,从0开始)就是1。因此整个数组根据第1位是0还是1分成两组。

a[0] =1  0x0001  第一组

a[1] =1  0x0001  第一组

a[2] =3  0x0011  第二组

a[3] =5  0x0101  第一组

a[4] =2  0x0010  第二组

a[5] =2  0x0010  第二组

第一组有{1,1,5},第二组有{3,2,3},然后对这二组分别执行“异或”解法就可以得到5和3了。

代码:

时间复杂度O(n),空间复杂度O(1)

class Solution {
    public int[] singleNumber(int[] nums) {
        int [] res = new int [2];
        if (nums == null || nums.length < 2) {
            return res;
        }
        int xorRes = 0;
        for (int x : nums) {
            xorRes ^= x;
        }
        int temp = 1; // 用来标志第几位是 1
        while (true) {
            if ((xorRes & 1) == 1) {
                break;
            }
            temp = temp << 1;
            xorRes = xorRes >> 1; // 右移,从低到高
        }

        for (int y : nums) {
            if ((y & temp) == 0) { // 对应位是 0
                res[0] ^= y;
            } else {
                res[1] ^= y;
            }
        }
        return res;
    }
}

Result:

Runtime:1ms

Your runtime beats 100% of java submissions.

大佬们,记得随手关注下我的公众号哦!见开篇二维码,一起嘿嘿嘿

------至所有正在努力奋斗的程序猿们!加油!!
有码走遍天下 ***寸步难行
1024 - 梦想,永不止步!
爱编程 不爱Bug
爱加班 不爱黑眼圈
固执 但不偏执
疯狂 但不疯癫
生活里的菜鸟
工作中的大神
身怀宝藏,一心憧憬星辰大海
追求极致,目标始于高山之巅
一群怀揣好奇,梦想改变世界的孩子
一群追日逐浪,正在改变世界的极客
你们用最美的语言,诠释着科技的力量
你们用极速的创新,引领着时代的变迁

——乐于分享,共同进步,欢迎留言讨论
——Treat Warnings As Errors
——Any comments greatly appreciated
——Talking is cheap, show me the code
——微信公众号:张氏文画