數(shù)組系列文章也到尾聲了御板，這是數(shù)組系列的最后一篇文章，后面就是樹(shù)的內(nèi)容了虚吟，如果后面又看到了相關(guān)的題目再作補(bǔ)充吧寸认，歡迎繼續(xù)關(guān)注。

• 數(shù)組中的逆序?qū)?/li>
• 數(shù)組中只出現(xiàn)一次的數(shù)字
• 在遞增排序的數(shù)組中查找和為s的兩個(gè)數(shù)字

1.數(shù)組中的逆序?qū)?/h2>

問(wèn)題描述：數(shù)組中的兩個(gè)數(shù)字串慰，如果前一個(gè)數(shù)字大于后面的數(shù)字偏塞，那么這兩個(gè)數(shù)組就組成一個(gè)逆序?qū)Γ斎胍粋€(gè)數(shù)組邦鲫，計(jì)算數(shù)組中的逆序?qū)Φ目倲?shù)灸叼。例如，數(shù)組{7,5,6,4}庆捺，有5對(duì)逆序?qū)沤瘢謩e是{7,6},{7,5},{7,4},{6,4},{5,4}.

算法思想

思路一：最簡(jiǎn)單的思路就是順序遍歷數(shù)組，沒(méi)遍歷到一個(gè)數(shù)字滔以，就將這個(gè)數(shù)字和后面的元素依次比較捉腥，統(tǒng)計(jì)逆序?qū)Φ臄?shù)目，但是這樣的思路時(shí)間耗費(fèi)比較嚴(yán)重你画，每個(gè)元素都需要進(jìn)行O(n)次比較抵碟，而總的元素個(gè)數(shù)是n，總時(shí)間復(fù)雜度就是O(n^2).
思路二：嘗試更快的解決方法坏匪。首先拟逮，逆序?qū)ζ鋵?shí)也就是比較大小，說(shuō)到比較大小剥槐，排序我們應(yīng)該很熟悉唱歧，那我們能不能在排序的過(guò)程中計(jì)算逆序?qū)Φ臄?shù)目呢宪摧？考慮這樣一個(gè)比較過(guò)程粒竖，先將數(shù)組分為長(zhǎng)度為2的兩個(gè)子數(shù)組，然后再將子數(shù)組分為長(zhǎng)度為1的子數(shù)組几于，接下來(lái)比較大小蕊苗，針對(duì)第一個(gè)子數(shù)組，得到{7,5}這一對(duì)逆序?qū)ρ嘏恚賹㈤L(zhǎng)度為1的子數(shù)組合并并排序朽砰，最后將長(zhǎng)度為2的子數(shù)組合并/排序，在這個(gè)過(guò)程中我們又可以再次計(jì)算逆序?qū)Φ臄?shù)目，將兩個(gè)相鄰子數(shù)組的最大的數(shù)進(jìn)行比較7和6瞧柔，前面的大數(shù)>后面的大數(shù)漆弄，逆序?qū)?shù)目+2，然后將較大的數(shù)7放到輔助數(shù)組中造锅，再比較下一對(duì),5和6進(jìn)行比較撼唾，前面的數(shù)小于后面的數(shù)，沒(méi)有逆序?qū)Ω缥担瑢⑤^大的數(shù)放到輔助數(shù)組中倒谷，接下來(lái)比較5和4，存在逆序?qū)Σ诠浚?是后面數(shù)組中最小的數(shù)字渤愁，所以逆序?qū)?1，再將大的數(shù)加入輔助數(shù)組中深夯，最后得到排好序的數(shù)組抖格，如下圖。

找數(shù)組中的逆序?qū)Φ倪^(guò)程

合并過(guò)程中計(jì)算逆序?qū)Φ倪^(guò)程

很明顯咕晋，這是一個(gè)歸并排序的過(guò)程他挎，在歸并的過(guò)程中計(jì)算逆序?qū)Φ臄?shù)目。歸并排序的時(shí)間復(fù)雜度是O(nlog),要比順序判斷的效率高捡需。

代碼

接下來(lái)办桨，我們就基于歸并排序統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。

//計(jì)算數(shù)組中逆序?qū)Φ臄?shù)目站辉，返回結(jié)果
int InversePairs(int data[], int length)
{
    if(data == NULL || Length <= 0)
    {
        fprintf(stderr, "Invalid parameter.\n");
        exit(1);
    }
    int copy[] = new int[length];
    for (int i = 0; i < length; i++)
        copy[i] = data[i];

    int count = InversePairsCore(data, copy, 0, length - 1);
    delete copy[];
    return count;
}

//用歸并排序計(jì)算逆序?qū)?shù)目呢撞，在歸并時(shí)計(jì)算逆序?qū)?返回結(jié)果是逆序?qū)Φ臄?shù)目
int InversePairsCore(int data[], int *copy, int start, int end)
{
    if (start == end)
        return 0;//當(dāng)子數(shù)組中只有一個(gè)數(shù)字時(shí)，不存在逆序?qū)?
    int mid = (start + end) / 2;//start~mid是前一半子數(shù)組饰剥，mid+1~end是后一半子數(shù)組
    int leftCount = InversePairsCore(data, copy, start, mid);//計(jì)算前一半子數(shù)組中逆序?qū)Φ臄?shù)目
    int rightCount = InversePairsCore(data, copy, mid + 1, end);//計(jì)算后一半子數(shù)組中逆序?qū)Φ臄?shù)目

    //歸并
    int i = mid;//定位到前一半子數(shù)組的最后一位殊霞，也就是最大的數(shù)字，從最大的數(shù)字開(kāi)始比較
    int j = end;//定位到后一半子數(shù)組的最大數(shù)
    int indexCopy = end;//輔助數(shù)組從當(dāng)前合并的數(shù)組的最高位開(kāi)始更新
    int count = 0;
    while (i >= start && j >= (mid + 1))//從最高位往前比
    {
        if (data[i] > data[j])//存在逆序?qū)?        {
            copy[indexCopy--] = data[i--];//將當(dāng)前比較得到的較大數(shù)保存到輔助數(shù)組
            count += j - mid;//當(dāng)前后一半數(shù)組中小于data[i]的元素個(gè)數(shù)
        }
        else 
            copy[indexCopy--] = data[j--];
    }
    while (i >= start)
        copy[indexCopy--] = data[i--];
    while (j >= mid + 1)
        copy[indexCopy--] = data[j--];
    //將copy中排好序的部分復(fù)制到原數(shù)組中
    for (int i = end; i > indexCopy; i--)
        data[i] = copy[i];
    //左半子數(shù)組中逆序?qū)Φ臄?shù)目+右半子數(shù)組中逆序?qū)Φ臄?shù)目+合并時(shí)逆序?qū)Φ臄?shù)目
    return leftCount + rightCount + count;
}

小結(jié)

這一道題的解決思路主要就是在利用歸并排序計(jì)算逆序?qū)Φ臄?shù)目汰蓉，和歸并排序相比绷蹲，不過(guò)是多了計(jì)算count的部分，歸并算法是關(guān)鍵算法顾孽∽８郑總結(jié)一下，若厚，就當(dāng)做是復(fù)習(xí)歸并排序了拦英。歸并算法是一種穩(wěn)定排序算法，也就是說(shuō)测秸，原數(shù)組中相等的兩個(gè)數(shù)疤估，排序之后兩個(gè)數(shù)的順序不會(huì)改變灾常，它主要是用分治的思想，將待排數(shù)組分成2個(gè)子數(shù)組铃拇，子數(shù)組再往下分钞瀑，每次分割都是一樣的，從中間位置開(kāi)始分慷荔，很明顯這是一個(gè)遞歸過(guò)程仔戈，當(dāng)分到子數(shù)組中只有一個(gè)數(shù)字的時(shí)候就結(jié)束了，這就是邊界條件拧廊。將數(shù)組分成子數(shù)組的時(shí)間復(fù)雜度是O(logn)监徘，這個(gè)過(guò)程很像在畫(huà)二叉樹(shù)，而每次將子數(shù)組合并需要O(n)吧碾，所以總的時(shí)間復(fù)雜度是O(nlogn)凰盔，而歸并排序需要一個(gè)O(n)的輔助數(shù)組來(lái)暫時(shí)存儲(chǔ)排好序的數(shù)組，所以空間復(fù)雜度是O(n)倦春。

2.數(shù)組中只出現(xiàn)一次的數(shù)字

問(wèn)題描述：輸入一個(gè)數(shù)組户敬，數(shù)組中除了兩個(gè)數(shù)字以外，其他數(shù)字都出現(xiàn)了兩次睁本，而這兩個(gè)數(shù)字只出現(xiàn)一次尿庐，找出這兩個(gè)只出現(xiàn)一次的數(shù)字。

算法思想

關(guān)注問(wèn)題中呢堰，有的數(shù)字只出現(xiàn)一次抄瑟，有的數(shù)字出現(xiàn)兩次，再聯(lián)系異或運(yùn)算枉疼，一個(gè)數(shù)字和它本身異或結(jié)果為0,而0和任何數(shù)異或結(jié)果是任何數(shù)皮假。假設(shè)另一種情況，假如數(shù)組中只有一個(gè)數(shù)字只出現(xiàn)一次骂维，其他都出現(xiàn)兩次惹资，我們可以順序異或數(shù)組中的各位，這樣數(shù)組中相同的數(shù)字都抵消了航闺，結(jié)果為0褪测，最后的結(jié)果就是那個(gè)值出現(xiàn)一次的數(shù)字，a^ba^cd^cb = d潦刃。

如果數(shù)組中存在兩個(gè)只出現(xiàn)一次的數(shù)字呢侮措，這樣我們順序異或數(shù)組中各個(gè)元素的得到的結(jié)果是這樣的，a^ba^cd^cb^e = d^e福铅，很明顯這不能確定最后的結(jié)果萝毛，那么如果我們將數(shù)組分為兩個(gè)子數(shù)組呢，讓兩個(gè)只出現(xiàn)一次的數(shù)字分別位于兩個(gè)子數(shù)組中滑黔，而其他的數(shù)字都成對(duì)出現(xiàn)的子數(shù)組中笆包，這樣分別對(duì)兩個(gè)子數(shù)組進(jìn)行異或操作就可以得到兩個(gè)只出現(xiàn)一次的數(shù)字了，接下來(lái)的問(wèn)題就是如何將原數(shù)組分開(kāi)呢略荡？

嘗試?yán)蒙弦淮萎惢虻慕Y(jié)果d^e庵佣，在d!=e的情況下，異或的結(jié)果一定不會(huì)是0汛兜，這個(gè)結(jié)果的二進(jìn)制表示中一定有一位是1巴粪，假設(shè)第k位是1，也就是說(shuō)d和e的二進(jìn)制表示下第k位一定不一樣(這樣才能保證異或之后結(jié)果為1),我們利用k這個(gè)數(shù)將數(shù)組分成兩個(gè)子數(shù)組粥谬，每個(gè)元素二進(jìn)制的第k為1的分到一個(gè)數(shù)組num1中肛根，為0的分到數(shù)組num2中，這樣能保證d和e一定能被分來(lái)漏策，而且相同的數(shù)字的二進(jìn)制表示第k位肯定是相同的派哲，所以相同的數(shù)字會(huì)被分到一個(gè)數(shù)組中，最后在分別對(duì)兩個(gè)數(shù)組依次進(jìn)行異或掺喻，就可以得到最后的結(jié)果芭届。

代碼

分析清楚之后代碼就簡(jiǎn)單多了，下面的代碼中將原數(shù)組拆分到兩個(gè)子數(shù)組操作簡(jiǎn)化了感耙，直接進(jìn)行異或操作得到結(jié)果褂乍。

int FindFirstBitIs1(int num);
bool isBit1(int num, int index);

//找到數(shù)組中只出現(xiàn)1次的兩個(gè)數(shù)字
//num1和num2用來(lái)保存最后的結(jié)果
void FindNumsAppearOnce(int data[], int length, int *num1, int *num2)
{
    if (data == NULL || length <= 0 || num1 == NULL || num2 == NULL)
    {
        fprintf(stderr, "Invalide parameter.\n");
        exit(1);
    }
    //對(duì)數(shù)組中的元素依次進(jìn)行異或
    int result = 0;//0和任何數(shù)異或結(jié)果為任何數(shù)
    for (int i = 0; i < length; i++)
        result ^= data[i];

    //d^e，找到這個(gè)結(jié)果的二進(jìn)制表示中的第一個(gè)1
    int indexOf1 = FindFirstBitIs1(result);

    *num1 = *num2 = 0;//初始化為0即硼，在拆分?jǐn)?shù)組的同時(shí)進(jìn)行異或運(yùn)算
    for (int i = 0; i < length; i++)
    {
        //將indexOf1為1的數(shù)組分到num1中
        if (isBit1(data[i], indexOf1))
            *num1 ^= data[i];
        else
            *num2 ^= data[i];
    }
}

//找到num中的第一個(gè)1逃片，返回下標(biāo)
int FindFirstBitIs1(int num)
{
    int index = 0;
    //判斷num最右邊的一位是不是0,一個(gè)int變量的二進(jìn)制表示最多有sizeof(int) * 8)位
    while ((num & 1) == 0 && (sizeof(int)* 8) > index)
    {
        num = num >> 1;//右移一位
        index++;
    }
    return index;
}

//判斷num的二進(jìn)制表示的第index位是不是1
bool isBit1(int num, int index)
{
    num = num >> index;
    return (num & 1);
}

小結(jié)

這一題在解決“數(shù)組中有兩個(gè)只出現(xiàn)一次的數(shù)字”這一問(wèn)題以外，還解決了“數(shù)組中只有一個(gè)只出現(xiàn)一次的數(shù)字”只酥，如果問(wèn)題變成题诵，數(shù)組中除了一個(gè)數(shù)字值出現(xiàn)一次，其他數(shù)字都出現(xiàn)3次呢层皱？

這個(gè)時(shí)候再用異或就不能解決問(wèn)題了性锭，換個(gè)角度，用位運(yùn)算來(lái)解決問(wèn)題叫胖，假設(shè)數(shù)組中所有的數(shù)字都出現(xiàn)了3次草冈，那么這些數(shù)字的二進(jìn)制各位上的1相加都是能被3整除，要么是3的倍數(shù)瓮增，要么是0怎棱，此時(shí)再對(duì)該數(shù)組添加任何一個(gè)數(shù)，如果這個(gè)數(shù)在二進(jìn)制的某位上為1都將導(dǎo)致該位上1的個(gè)數(shù)不能被3整除绷跑，因此通過(guò)統(tǒng)計(jì)二進(jìn)制上每位1的個(gè)數(shù)就可以推斷出x在該位置上是0還是1了拳恋，這樣就能計(jì)算出x了，原文鏈接（附代碼） 砸捏。

3.在遞增排序的數(shù)組中查找和為s的兩個(gè)數(shù)字

問(wèn)題描述：輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字s谬运，在數(shù)組中查找兩個(gè)數(shù)隙赁，使它們的和加起來(lái)正好是s，如果有多組這樣的數(shù)梆暖，任意輸出一對(duì)即可伞访。例如輸入數(shù)組{1,2,4,7,11,15}和數(shù)字15，由于4+11=15轰驳，因此輸出4和11.

算法思想

思路一：O(n^2)的方法厚掷，首先確定一個(gè)數(shù)字，然后遍歷數(shù)組中其余(n-1)個(gè)數(shù)字级解，判斷它們的和是不是s冒黑，這是最簡(jiǎn)單也是最快想到的方法，很明顯勤哗，這一種算法的時(shí)間復(fù)雜度會(huì)很高抡爹，所以我們需要找一種更快的方法.

思路二：利用排序數(shù)組的這一特點(diǎn)，先選擇兩個(gè)數(shù)字俺陋，如果兩個(gè)數(shù)字的和等于s豁延，那么我們就找到了要找的兩個(gè)數(shù)字，如果和小于s腊状，我們希望和再大一些诱咏，可以選擇較小的數(shù)字后面的數(shù)，因?yàn)閿?shù)組是排好序的缴挖，排在后面的數(shù)字一定大于或等于前面的數(shù)字袋狞，就有可能找這兩個(gè)數(shù)字；同樣的映屋，如果和大于s苟鸯，就選擇較大的數(shù)字前面的數(shù)字。

就數(shù)組{1,2,4,7,11,15}和期待數(shù)字15來(lái)說(shuō)棚点，先定義兩個(gè)指針早处，第一個(gè)指針指向第一個(gè)數(shù)字，第二個(gè)指針指向最后一個(gè)數(shù)字瘫析，這兩個(gè)指針的和是16砌梆，我們移動(dòng)第二個(gè)指針，使其指向11贬循，這時(shí)和是1+11是12咸包，小于15，接下來(lái)移動(dòng)第一個(gè)指針杖虾，指向2烂瘫，這時(shí)的和是2+11是13,仍然小于15,接下來(lái)移動(dòng)第一個(gè)指針，指向2,計(jì)算和是4+11=15,這樣就找到了我們要找的兩個(gè)數(shù)字奇适。

這一種算法是從兩邊想中間掃描坟比，在while循環(huán)內(nèi)完成查找任務(wù)芦鳍，所以時(shí)間復(fù)雜度是O(n).

代碼

注：用64位長(zhǎng)整型接收相加的結(jié)果，避免越界錯(cuò)誤温算。

//在data數(shù)組中找到num1和num2怜校，它們的和是sum间影，數(shù)組長(zhǎng)度為length
bool FindNumbersWithSum(int data[], int length, int sum,
int* num1, int* num2)
{
    bool found = false;
    if (data == NULL || length <= 0 || num1 == NULL || num2 == NULL)
    {
        fprintf(stderr, "Invalid parameter.\n");
        return found;
    }

    int ahead = length - 1;
    int behind = 0;
    while (ahead >= behind)
    {
        long long temp = data[ahead] + data[behind];
        if (temp == sum)
        {
            *num1 = data[behind];
            *num2 = data[ahead];
           found = true;
            break;
        }
        else if (temp < sum)
            behind++;
        else
            ahead--;
    }

    return found;
}

總結(jié)

數(shù)組系列就到這里了注竿，這一篇只寫(xiě)了2道題，篇幅也較小魂贬。在數(shù)組中的逆序?qū)?/strong>中巩割，是用歸并排序來(lái)解決問(wèn)題，在排序同時(shí)計(jì)算逆序?qū)Φ臄?shù)目付燥，而在數(shù)組中只出現(xiàn)一次的數(shù)字是用到了位運(yùn)算的知識(shí)宣谈，這里就簡(jiǎn)單帶過(guò)了，之后再補(bǔ)上位運(yùn)算算法題的總結(jié)键科。最近耽擱的時(shí)間有點(diǎn)久闻丑，后面的算法題我會(huì)加緊跟上，歡迎繼續(xù)關(guān)注~