Single Number I II III

一系列关于位操作的问题。

Single Number I II III Single Number Single Number II Single Number III

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?

Given [1,2,2,1,3,4,3], return 4

Leetcode:136. Single Number

Lintcode:82. Single Number

本题要求在指定数组中找出只出现一次的元素，其中该数组有2n+1个元素且除要找出元素外均只出现两次。

还知道异或运算有如下特性：

即在A⊕B 时,若有A=B,则A⊕B=0。

又知A⊕B=B⊕A,即满足交换律。

可知，A1⊕A2⊕?⊕An=B,其中B为只出现一次的元素。

class Solution {
public:
    int singleNumber(vector& nums) {
        int res = 0;
        for (int a : nums) {
            res ^= a;
        }
        return res;
    }
};

Single Number II

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?

Given [1,1,2,3,3,3,2,2,4,1] return 4

Leetcode:137. Single Number II

Lintcode:83. Single Number II

本题是上一题的加强版，很显然不再是一道可以用异或简单求得答案的题了。

但是，仍可以使用二进制位的思想。

这一回将所有整数看做二进制数，则每一位有两种可能 0 或 1

题中数组除要找到的元素只出现一次外，其他元素均恰好出现3次。

所以，只要记录在整个数组中整数各位的数值就可以得到只出现一次的整数的二进制位数分布情况。

class Solution {
public:
    int singleNumber(vector& nums) {
        vector bits(sizeof(int) * 8 , 0);
        for (int a : nums) {
            for (int i = 0 ; i < bits.size() ; i ++) {
                bits[i] += (a & 1);
                a >>= 1;
            }
        }
        int res = 0;
        for (int i = bits.size() - 1 ; i >= 0 ; i --) {
            res <<= 1;
            res |= (bits[i] % 3);
        }
        return res;
    }
};

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.

2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

本题是第一题的变种，与第二题关联不大。要使其被归化为问题一需要对数组进行分化。

这也是本题的关键。

能很明显地看出单纯的对数组进行异或，会得到目标数A和B的异或A⊕B

这个数的二进制数中的 1 代表了A和B中其中一个在该位上为 0 另一个在该位上为 1

这样就可以用该数的任意一个含 1 位来区分A和B

同时，又知由于其他元素恰好出现两次。这些元素在上述的那个二进制位上也有 0和1两种情况，即用该位分划也会将无关元素分为两组。

但是，这并不会将某一元素出现的两次分到不同组中。

所以，至此可以确定，通过A⊕B在二进制表示中一个带 1 的位，可以将数组分成两个问题一中的数组。

在这里为了快速地得到为 1 的位，我们采用将diff 和 -diff做与操作（这里都使用补码表示）

这里利用了补码取负时从后向前数的第一个不为 0 的数不会变得特性，取得了diff中第一个不为 0 的位。

class Solution {
public:
    vector singleNumber(vector& nums) {
        int diff = 0;
        for (int a : nums) {
            diff ^= a;
        }
        diff &= -diff; //得到diff中一个二进制为一的位
        vector res(2 , 0);
        for (int a : nums) {
            if ((a & diff) == 0)
                //被分到在该位为0的一组
                res[0] ^= a;
            else
                //被分到在该位为1的一组
                res[1] ^= a;
        }
        return res;
    }
};