找出数组中唯一不同的数

一个数组中只有一个数是唯一的，其他数都是成对出现，找出这个唯一的数

要求时间复杂度为o(n),空间复杂度为o(1)
分析：由于位运算符异或运算的特点，即两个相同的数进行异或运算时，其结果为0，所以当将数组中所有的元素进行异或运算时，其结果必定为那个唯一的数。
代码如下：

int findOnlyNum(int arr[], int len) {
    int result = 0;
    for (int i = 0; i < len; i++)
    {
        result = result ^ arr[i];
    }
    return result;
}

一个数组中有两个数是不同的，其他数都是成对出现，找出这两个不同的数

要求时间复杂度为o(n),空间复杂度为o(1)
分析：当两个数不同时，其二进制位必定有一位是不同的，我们可以找出这个二进制位，并将数组分成两个子数组，保证每个数组中只有一个数是唯一的，这样就会变成问题一的情况。
代码实现如下：

void findTwoDifNums(int arr[], int len, int& num1, int& num2) {
    int sum = 0;
    for (int i = 0; i < len; i++)
    {
        sum ^= arr[i];
    }

    int firstBit = findFirstBit(sum);

    for (int i = 0; i < len; i++)
    {
        int num = arr[i] >> firstBit;
        if (num & 1) 
        {
            num1 ^= arr[i];
        }
        else
        {
            num2 ^= arr[i];
        }
    }
}

int findFirstBit(int num) {
    int firstBit = 0;
    //注意这里有个容易出错的地方，由于位运算符的优先级低于等号，所以必须对 num & 1加括号，
    //若写成 num & 1 == 0,则是错误的，其结果是无法进入while循环。
    while (((num & 1) == 0) && (firstBit < 8 * sizeof(int)))
    {
        num = num >> 1;
        firstBit++;
    }
    return firstBit;
}

测试代码如下：

void main() {

    int arr[9] = { 2, 3, 4, 9, 4, 3, 9, 2, 8 };

    int value = findOnlyNum(arr, sizeof(arr) / sizeof(int));

    cout << "The different value is " << value << endl;

    int arr2[10] = { 2, 3, 4, 9, 6, 4, 3, 9, 2, 8 };

    int num1 = 0;
    int num2 = 0;

    findTwoDifNums(arr2, sizeof(arr2) / sizeof(int), num1, num2);

    cout << "The different two values is " << num1 <<"   "<<num2 << endl;

    getchar();
}

运行结果如下：

image.png

引自： 《剑指offer》