C語言實(shí)現(xiàn)一個(gè)int類型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次，找出這兩個(gè)數(shù)字

題目是這樣敘述的：
在一個(gè)數(shù)組中除兩個(gè)數(shù)字只出現(xiàn)1次外，其它數(shù)字都出現(xiàn)了2次， 要求盡快找出這兩個(gè)數(shù)字。

要求：時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)。

請(qǐng)看我的分析：
將這道題簡(jiǎn)單化：
一個(gè)數(shù)組中只有一個(gè)數(shù)字出現(xiàn)一次，其他數(shù)字都是成對(duì)出現(xiàn)的，這時(shí)我們可以根據(jù)異或運(yùn)算符的特性：A^B^A = B; 0 ^ A = A；我們可以將這個(gè)數(shù)組的全部元素依次做異或運(yùn)算，最終結(jié)果就是那個(gè)只出現(xiàn)一次的數(shù)字。
不會(huì)的可看本人（2019-04-04）那天的博客

如果這個(gè)數(shù)組中出現(xiàn)兩個(gè)不同的數(shù)字，而其他數(shù)字均出現(xiàn)兩次，假設(shè)這兩個(gè)數(shù)字分別是x, y。那如果可以將x, y分離到兩個(gè)數(shù)組。這時(shí)這道題就變成兩個(gè)我們簡(jiǎn)化之后的版本中的數(shù)組了。這樣問題就可以得到解決了。由于x，y肯定是不相等的，因此在二進(jìn)制上必定至少有一位是不同的。根據(jù)這一位是0還是1可以將x，y分開到A組和B組。并且數(shù)組中其他元素也可以根據(jù)這個(gè)方法劃分到兩個(gè)數(shù)組中。這時(shí)將兩個(gè)數(shù)組分別做異或運(yùn)算，結(jié)果就是這兩個(gè)數(shù)字。

#include<stdio.h>

#define SIZE(arr) sizeof(arr)/sizeof(arr[0])

void find_num(int *arr, int len,int *num1,int *num2)
{
    int i;
    int sum = 0;
    for (i = 0; i < len; i++)
    {
        sum^=*(arr + i);//異或出所有數(shù)字
    }
    int j;
    for (j = 0; j < sizeof(int)* 8; j++)//int類型數(shù)組的字節(jié)數(shù)32
    {
    //if(sum>>j&1==1)也正確，不知道優(yōu)先級(jí)，盡量加上，下面一樣
        if (((sum >> j) & 1) == 1)//說明sum在右移 j 個(gè)單位后，二進(jìn)制不一樣
        {
            break;
        }
    }
    for (i = 0; i < len; i++)
    {
        if (((*(arr + i) >> j) & 1) == 1)
        {
            *num1 ^= (*(arr + i));//異或 j 位置為1的一組數(shù)字
        }
        else
        {
            *num2 ^= (*(arr + i));//異或 j 位置為0的一組數(shù)字
        }
    }
}

int main()
{
    int arr[] = { 1, 3, 5, 7, 1, 3, 5, 9 };
    int num1=0, num2=0;
    find_num(arr,SIZE(arr),&num1,&num2);
    printf("%d %d", num1, num2);
    return 0;
}

總結(jié)：復(fù)雜問題簡(jiǎn)單化，把兩個(gè)出現(xiàn)一次的數(shù)字分割為兩組出現(xiàn)一次的數(shù)組