[LeetCode] 136.SingleNumber 和 13

136 SingleNumber

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?

这个问题很经典，变体也多。
最容易想到的做法肯定是开一个HashMap存每个数字出现的次数。
但是要求是O(n)的复杂度，没有额外的空间开销。
其实自己想很难想到，看了题解之后大多数人的感觉是还有这种操作？

就是用一个0和每个元素取异或，一个数异或自己为0，所以出现两次的数异或之后为0，而出现一次的数则保留了下来。
看代码：

public int singleNumber(int[] nums) {
        int i = 0;
        for (int num : nums) {
            i ^= num;
        }
        return i;
    }

137 Single Number II

LeetCode很有意思，出了1之后可能还有2，3都是变体，难度会增加，有时候思路完全不一样。

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

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

这个说实话也是很难想到的，但是还是基于的位运算。
给出discuss中第一名的答案：

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

这个解法斟酌一下，大致思路就是：
一个数出现第一次的时候存在ones中，出现第二次的时候存在twos中，出现第三次的时候在ones中被清0。所以最后保留的就是出现一次的数。

540. Single Element in a Sorted Array

上面一题其实已经很枯燥了，不过这一题很有意思。

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

** Note** : Your solution should run in O(log n) time and O(1) space.

给出一个已经排序过的数组，除了一个数只出现了一次，其他的数都出现了两次。
其实用137题的写法也是可以的。
但是我们浪费了它已经排序过这个条件了。
再看看复杂度给的是O(lgn)
很容易想到的是二分。

public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length / 2;
        while (left < right) {
           int mid = left + (right - left)/2; 
            if (nums[mid * 2] == nums[mid * 2 + 1]) {
               left = mid+1;
           }
           else {
               right = mid;
           }
        }
        return nums[left * 2];
    }