求缺省數(shù)字時可以使用異或進行求解，時間復雜度為O(N)。

我們都知道，異或的特點就是相同為0，相異為1 ，比如：

這是3和3相異或的結果，為0， 同樣地，有4^4 = 0,5^5 = 0等等……

這也是我們思考這道題的出發(fā)點：

既然相同異或就為0，那么我們是不是只要將此數(shù)組與一個完整數(shù)組（個人習慣稱為完全數(shù)組）挨個求異或，相同的數(shù)字就會被異或沒，剩下的那個數(shù)字（這個數(shù)字是在完全數(shù)組中留下的）是不是就是題給數(shù)組的缺省數(shù)字？

答案是肯定的：

此時剩下的數(shù)字就是4即為所求。

但是我們怎么樣用代碼去實現(xiàn)呢？

本質上是兩兩求異或，非要兩個數(shù)組的數(shù)字對應相異或嗎？（1-1,2-2,3-3,5-5,6-6,7-7）

我們可以很快的實現(xiàn)一個完全數(shù)組的創(chuàng)建，找到缺省數(shù)組的最小值，往后加（N+1）個數(shù)便可得到，但是如果題給的數(shù)組是亂序呢？我們無法做到一一對應去求異或。

于是，奇妙的異或運算便替我們省去了很多步驟。

異或運算是有交換律的，即：a⊕b = b⊕a;

難理解的話我們來看一個例子：

假如現(xiàn)在有一個數(shù)組：{1,2,1,3,4}；其中有兩個 1 重復了，我已如果對這個數(shù)組進行兩兩異或結果是不是應該為2^3^4的值呢？

很顯然，異或消去相同數(shù)并不需要對應，只要讓這個數(shù)字最終和一個跟它相同的數(shù)字異或就可以消去；所以，我們可以將完全數(shù)組與缺省數(shù)組混合起來成為一個數(shù)組兩兩異或，就可以求出那個缺省數(shù)字。

思想就是這個樣子，但是在實現(xiàn)時，如果要將兩個數(shù)組合并為一個數(shù)組又得有多余的步驟，所以我的做法是將兩個數(shù)組各自兩兩異或、得到結果A和結果B；再將A與B異或得到缺省數(shù)字。

拙解

#include <stdio.h>
int fun(int arr[], int len);
int main() 
{
    int arr[] = { 78, 79, 81, 83, 82, 84 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int res = fun(arr, len);
    printf("%d\n", res);
    return 0;
}
int fun(int arr[], int len)
{
    int i, j;
    int temp1 = 0, temp2 = 0;
    int min = arr[0];
    //確定完全數(shù)組起始值
    for (i = 0; i < len; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    //對完全數(shù)組進行異或
    for (j = min; j < (len + 1)+min; j++)
    {
        temp1 ^= j;
    }
    //對原始（缺數(shù)）數(shù)組進行異或
    for (i = 0; i < len; i++)
    {
        temp2 ^= arr[i];
    }
    int res = temp1 ^ temp2;
    return res;
}

到此這篇關于C語言計算連續(xù)無序數(shù)組中缺省數(shù)字方法詳解的文章就介紹到這了,更多相關C語言無序數(shù)組中缺省數(shù)字內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論