[LeetCode]--136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

耐心看下我的思想演变过程吧，可能是大脑缺氧，用List装下标。

public int singleNumber(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (temp.contains(i))
                continue;
            for (int j = i + 1; j < nums.length; j++) {
                if (temp.contains(j))
                    continue;
                if (nums[i] == nums[j]) {
                    System.out.println(i + "---" + j);
                    temp.add(i);
                    temp.add(j);
                    break;
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (!temp.contains(i)) {
                return nums[i];
            }
        }
        return 0;
    }

代码逻辑和实现应该没有问题，测试也通过了，就是提交的时候超时了，于是我就想着用空间去换取时间。

public int singleNumber1(int[] nums) {
        ArrayList<Integer> preList = new ArrayList<Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        int len = nums.length;
        int[] flag = new int[len];
        Arrays.fill(flag, 0);
        for (int i = 0; i < len; i++) {
            if (!preList.contains(nums[i])) {
                preList.add(nums[i]);
            } else {
                flag[i] = 1;
            }
            if (!list.contains(nums[len - 1 - i])) {
                list.add(nums[len - 1 - i]);
            } else {
                flag[len - 1 - i] = 1;
            }
        }
        for (int i = 0; i < flag.length; i++) {
            if (flag[i] == 0) {
                return nums[i];
            }
        }
        return 0;
    }

这也是一种方法其实，两头同时遍历，一次遍历就可以解决问题，但是仔细想想其实复杂度没减。

再使用暴力搜索，遍历数组，发现两个元素相等，则将这两个元素的标志位置为1，最后返回标志位为0的元素即可。时间复杂度O(n^2)没有AC，Status:Time Limit Exceed

public int singleNumber2(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return nums[0];
        int[] flag = new int[n];
        for (int i = 0; i < n; i++) {
            if (flag[i] == 1)
                continue;
            else {
                for (int j = i + 1; j < n; j++) {
                    if (nums[i] == nums[j]) {
                        flag[i] = 1;
                        flag[j] = 1;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (flag[i] == 0)
                return nums[i];
        }
        return 0;
    }

后来用这个就是通过的，Accept！真是高兴，但是又不服，这个其实和第一次一样，只是用数组装flag。而且我觉得很有可能是偶然通过的。

其实我记得有个位运算很简单也很高效。但是说实话，一般来说大家对位运算都有种神秘陌生对吧，我也不例外，虽然知道，但是用起来很困难。

利用异或操作。异或的性质1：交换律a ^ b = b ^ a，性质2：0 ^ a = a。于是利用交换律可以将数组假想成相同元素全部相邻，于是将所有元素依次做异或操作，相同元素异或为0，最终剩下的元素就为Single Number。时间复杂度O(n)，空间复杂度O(1)

public int singleNumber(int[] A) {
        if(A == null || A.length == 0) {
            return -1;
        }
        int rst = 0;
        for (int i = 0; i < A.length; i++) {
            rst ^= A[i];
        }
        return rst;
    }

所以还是强烈建议用后面这种。