算法-找出数组中唯一不同的数

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

使用异或运算

时间复杂度为o(n),空间复杂度为o(1)

两个操作数的位中，相同则结果为0，不同则结果为1。

一个数和0异或还是自己，一个数和自己异或是0。

分析：由于位运算符异或运算的特点，即两个相同的数进行异或运算时，其结果为0，所以当将数组中所有的元素进行异或运算时，其结果必定为那个唯一的数。

static void FindNumber(int[] array)
{
    int v = 0;
    for (int i = 0; i < array.Length; i++)
    {
        v ^= array[i];
    }
    Console.WriteLine("只出现一次的数是:" + v);
}

HashSet方式

static void FindNumberHashSet(int[] array)
{
    HashSet<int> set = new HashSet<int>(); 
    List<int> list = new List<int>();

    foreach (var t in array)
    {
        if(!set.Add(t))
            list.Add(t);
    }

    foreach (var t in set)
    {
        if(!list.Exists(o => o == t))
            Console.WriteLine("只出现一次的数是:" + t);
    }
}

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

时间复杂度为o(n),空间复杂度为o(1)

#include <fstream>
#include <iostream>
using namespace std;

int findFirstBit(int num)
{
    int firstBit = 0;

    while (((num & 1) == 0) && (firstBit < 8 * sizeof(int)))
    {
        num = num >> 1;
        firstBit++;
    }
    return firstBit;
}

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 main()
{
    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();

    return 0;
}

参考：
找出数组中唯一不同的数