1到n中減少了一個數，順序被打亂，找出缺失的數

2013年的創新工場筆試考了：http://blog.csdn.net/huangxy10/article/details/8026464

而且應該還是一道經典的筆試面試題：http://fayaa.com/tiku/view/2/

在上面連結中，有人給出如下幾種方法：

對于丢失一個數的情況： 

1）用1+2+...+n減去目前輸入資料的總和。時間複雜度：O(n) 空間複雜度：O(1) 【容易溢出】

2）用12...*n除以目前輸入資料的總積。時間複雜度：O(n) 空間複雜度：O(1) 【容易溢出】

3）用1^2^...^n的結果在逐個異或目前輸入資料。時間複雜度：O(n) 空間複雜度：O(1)

4）對輸入資料排序，然後從頭到尾周遊一次。時間複雜度O(nlogn) 空間複雜度O(1)

5) 對輸入資料進行Hash，然後從頭到尾周遊一次。時間複雜度O(n) 空間複雜度O(n)

第三種方法，個人認為是最為精妙的，因為相同的數取異或為0,0^0為0，是以最終按照該方法得到的數就是缺失的那個數。其算法複雜度準确的說為：Theta(2*n-1)。方法1和2，雖然簡單，且時間複雜度和空間複雜度都不錯，但可能因為n過大，存在溢出問題。4空間複雜度好，但是需要排序後再找，即使使用計數排序這種O(n)的排序方法（其實對于這道題，還是挺适合計數排序的），複雜度也是O（n）的樣子。方法5使用哈希算一遍要theta(n)，再周遊一遍，其實也是Theta(2*n-1)。

後三種都能解決問題，第三種較好。

經過思考，我也給出了另外一種Theta(2*n-1)的算法（哎，本來以為是Theta((lgn)^2)的，不過算了一下還是Theta(2*n-1)的）：

對于從1~n的數，減少了一個數，存在數組a[n-1]中，并且順序是亂的。

核心思想就是比較中位數位置和中位數元素的關系。基本思想是這樣的，首先找到數組a[n-1]的中位數，如果發現中位數與該位置是相等的，則說明中位數放在了正确的位置，那麼缺失的數肯定是要大于該中位數的（否則，中位數元素會比該位置大1），則缺失的數在中位數右側。如果不相等的話，則缺失的數一定在中位數左邊。确定了範圍之後，再繼續這樣遞歸查找，直到查找結束，其實這個算法有點像二分法和中位數查找的結合。這樣說可能不太明白，舉個例子：

例如，現在是1~10這10個數，a[9]={5,8,6,2,3,4,1,9,10};缺的是7這個數，那麼，這個數組如果排序的話應該是這樣的：

{1,2,3,4,5,6,8,9,10}，p=1,q=9,中位數位置r=(p+q)/2=5,而中位數元素是"5"，二者相等，說明5在正确的位置，缺失的數一定比5大。注意，這時候算法已經将5擺在正确的位置。繼續在大于5的數的序列中按此方法查找。

{6,8,9,10}  ，p=6,q=9,中位數位置r=(p+q)/2=7,而此時找到的中位數的元素是a[7]=8，二者不等，說明已經發現缺失的數，比8小。繼續在左側查找

這時候隻剩下{6}，p=6,q=6,r=(p+q)/2=6,則發現a[6]=6，是相等的。缺失的數在哪？事實上，對于在正好結束時，如果存在中位數和中位數元素相等的時候，那麼其實缺失的數就是最終結束的中位數右側的數，即比該數大1的數。是以遞歸最後結束的條件是這樣的。

if(p==q) {
        if(a[p]==p) return p+1;  //如果當p=q查找結束的時候，發現a[p]與p相等，其實說明缺失的數正好是該數右邊的數 
        else return p;           //如果不相等，則說明缺失的數正好是終止的位置的數（事實上，在這裡a[p]>p） 
    }
           

#include <stdlib.h>
#include <stdio.h>
#define N 10
#define NL 8   // NL為缺失的數 

void Swap(int *a, int *b){
    int tmp;
    tmp=*a;
    *a=*b;
    *b=tmp;
}

//快排中的劃分函數  
int Partition(int *a, int p, int q){
    int i,j,x=a[q];
    for(i=p-1,j=p;j<q;j++){
        if(a[j]<x){
            Swap(&a[j],&a[++i]);
        }
    }
    Swap(&a[j],&a[++i]);
    return i;
}

//找到從小到大排，排第pos個的數的值，在該算法中是找中位數的值 
int FindPos(int *a, int p, int q, int pos){
    if(p==q) return a[p]; 
    int r=Partition(a,p,q);
    if(r<pos) return FindPos(a,r+1,q,pos-r);
    else if(r>pos) return FindPos(a,p,r-1,pos);
    else return a[r]; 
}

//查找1-n中缺失的數 
int FindLost(int *a, int p, int q){
    if(p==q) {
        if(a[p]==p) return p+1;  //如果當p=q查找結束的時候，發現a[p]與p相等，其實說明缺失的數正好是該數右邊的數 
        else return p;           //如果不相等，則說明缺失的數正好是終止的位置的數（事實上，在這裡a[p]>p） 
    }
    int r=(p+q)/2;  //中位數位置 
    int realnum=FindPos(a,p,q,r);  //找到中位數位置實際的值 
    if(realnum == r) return FindLost(a,r+1,q);  //如果找到的真實的數與目前位置吻合，那麼缺失的數一定在右側
    else return FindLost(a,p,r-1);  //否則在左側找；
} 

int main(){
    int i,j;  
    int a[N]={-1,5,8,6,2,3,4,1,9,10};    
    for(i=1;i<N;i++){
        printf("%d ",FindPos(a,1,N,i));
    }
    printf("\n");    
    printf("缺失的數是%d ",FindLost(a,1,N-1));   
    system("pause");   
    return 0;
}
           

算法複雜度分析

時間複雜度：FindPos實際就是算法導論中給出的中位數查找（查找第n個最小值問題）的算法，其複雜度是theta(n)。之後，每次折半查找，算法複雜度=theta(n)+theta(n/2)+

theta(n/4)+……+theta(1)=theta(n*(1+1/2+1/4+1/lgn))=theta(n*(2-(1/2)^lgn))=theta(2n-1)（哎，折騰了半天，還是2n-1的），空間複雜度是O(1)。