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

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

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

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

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

答案是肯定的：

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

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

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

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

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

異或運(yùn)算是有交換律的，即：a⊕b = b⊕a;

難理解的話我們來看一個(gè)例子：

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

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

思想就是這個(gè)樣子，但是在實(shí)現(xiàn)時(shí)，如果要將兩個(gè)數(shù)組合并為一個(gè)數(shù)組又得有多余的步驟，所以我的做法是將兩個(gè)數(shù)組各自兩兩異或、得到結(jié)果A和結(jié)果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];
        }
    }
    //對(duì)完全數(shù)組進(jìn)行異或
    for (j = min; j < (len + 1)+min; j++)
    {
        temp1 ^= j;
    }
    //對(duì)原始（缺數(shù)）數(shù)組進(jìn)行異或
    for (i = 0; i < len; i++)
    {
        temp2 ^= arr[i];
    }
    int res = temp1 ^ temp2;
    return res;
}

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

最新評(píng)論