现在的位置: 首页 > 综合 > 正文

1到n中减少了一个数,顺序被打乱,找出缺失的数

2018年05月02日 ⁄ 综合 ⁄ 共 2666字 ⁄ 字号 评论关闭

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)。

抱歉!评论已关闭.