面试跟序列有关的问题汇总

　　面试中比较多会出序列有关的面试题，所以就总结下

（1）一个长度N为的序列，求前K小的数

　　1.排序 N*log(N)

　　2.最大堆N*log(K)

　　3.有平均时间复杂度O(n)的算法，因为我们可以在O(n)的时间内找到未排序数组里面第k小的数的值，然后再遍历一下数组，把值小于等于第k小的全都输出(感谢 huangnima)

（2）有两个长度为N的有序序列A和B，在A和B中各任取一个数可以得到N^2个和，求这N^2个和中最小的N个。

　　1.比较直观的想法是将A与B的数字相加后排序，时间复杂度O(N*N*log(N*N))

　　2.考虑到要求的是求最小的N个数字，所以从这里考虑优化，维护一个大小为N的最小堆 log(N)，对于N^N个数字的选择有没有优化方法，有！

　　　　可以把这些和看成n个有序表:

　　　　– A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…

　　　　– A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=…

　　　　–…

　　　　– A[n]+B[1] <= A[n]+B[2] <= A[n]+B[3] <=…

　　　　当然并不用计算所有的和

　　　　综上所述，可以采用K路归并：

　　　　就是最小堆的元素增加一个状态量（下标），记录当前列最小值所在位置，下次遍历时从这里开始！

　　　　总的时间复杂度O(N*log(N))

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;

struct data{
    int v;
    int no;
    data(int tv,int tno){
        v=tv;
        no=tno;
    }
    friend bool operator <(data x,data y){
        return x.v>y.v;
    }
};

int n;
int A[100099];
int B[100099];
int minS[100099];//记录最小的N个数字
int reD[100099];//记录相对最小的那个数字在所在行当前遍历的位置

int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF){
        int i;
        priority_queue<data>qq;
        for(i=1;i<=n;i++){
            scanf("%d",&A[i]);
        }
        for(i=1;i<=n;i++){
            scanf("%d",&B[i]);
        }

        for(i=1;i<=n;i++){
            qq.push(data(A[1]+B[i],i));
            reD[i]=1;
        }

        for(i=1;i<n;i++){
            minS[i]=qq.top().v;
            int no=qq.top().no;
            qq.pop();
            reD[no]++;
            qq.push(data(A[reD[no]]+B[no],no));
        }minS[i]=qq.top().v;

        for(i=1;i<=n;i++){
            printf("%d
",minS[i]);
        }
    }

    return 0;
}

View Code

(3)有两个有序序列长度分别N，M。在A和B中各任取一个数可以得到N*M个和，求这N*M个和某个数字K是第几大的元素。

　　1.暴力N*M排序，时间复杂度O(N*M*log(N*M))

　　2.贪心的思想：　随着i增大，j只会逐渐减小或不变，时间复杂度O(N+M)

　　注意查询的数字有多个相同数字的情况

#include<stdio.h>
int A[100099];
int B[100099];

int main()
{
    int n,m,k;
    while(scanf("%d",&n)!=EOF){
        int i,j;
        for(i=1;i<=n;i++){
            scanf("%d",&A[i]);
        }
        scanf("%d",&m);
        for(i=1;i<=m;i++){
            scanf("%d",&B[i]);
        }
        scanf("%d",&k);k--;
        j=m;
        int all=0;
        for(i=1;i<=n;i++){
            while(A[i]+B[j]>k){
                j--;if(j==0)break;
            }if(j==0)break;
            all+=j;
        }
        printf("%d
",all+1);
    }

    return 0;
}

View Code

(4)有两个有序序列长度分别N，M。在A和B中各任取一个数可以得到N*M个和，求这N*M个中第K大的元素是

　　Nmin，Mmin,Nmax,Mmax分别表示N，M的最小值域最大值

　　对[Nmin+Mmin,Nmax+Mmax]进行二分，二分出一个结果，判断这个值是第几大（第三个问题），再二分判读直到出结果

　　时间复杂度O(log(-Nmin-Mmin+Nmax+Mmax)*(N+M))

　　提供练习的传送门：http://ac.jobdu.com/problem.php?pid=1534

（5）查找一个数列中为K的个数有几个

　　1.如果有序两次二分，先找K最左端的位置，在二分k最右端的位置

#include<stdio.h>

int shu[1009];

int main()
{
    int n,i;
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++){
            scanf("%d",&shu[i]);
        }
        int f;
        scanf("%d",&f);
        int ll=1,rr=n,mid;
        while(ll<=rr){//尽量靠左
            mid=(ll+rr)/2;
            if(f<=shu[mid])rr=mid-1;
            else ll=mid+1;
        }
        int rll=ll,rrr;
        //printf("%d
",ll);

        ll=1,rr=n;
        while(ll<=rr){//尽量靠右
            mid=(ll+rr)/2;
            if(f<shu[mid])rr=mid-1;
            else ll=mid+1;
        }
    //    printf("%d
",rr);
        rrr=rr;

        if(shu[rll]!=f){
            printf("个数为0
");
        }else{
            printf("个数为 %d
",rrr-rll+1);
        }
    }

    return 0;
}

View Code

2.如果无序，则线性遍历

(6) 给定一个数字序列，查询任意给定区间内数字的最小值。

　　1.RMQ O(n*logn)

#include<stdio.h>
 
int A[100099],d[100099][20];
int n,m;
 
int min(int a,int b){
    return a<=b?a:b;
}
 
void RMQ_init(){
    int i,j;
    for(i=1;i<=n;i++)d[i][0]=A[i];
    for(j=1;(1<<j)<=n;j++){
        for(i=1;i+(1<<j)-1<=n;i++){
            d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
        }
    }
}
 
int RMQ_find(int ll,int rr){
    int k=0;
    while((1<<(k+1))<=(rr-ll+1))k++;
    return min(d[ll][k],d[rr-(1<<k)+1][k]);
}
 
int main(){
    while(scanf("%d",&n)!=EOF){
        int i,j;
        for(i=1;i<=n;i++){
            scanf("%d",&A[i]);
        }RMQ_init();
        scanf("%d",&m);
        int ll,rr;
        while(m--){
            scanf("%d%d",&ll,&rr);
            printf("%d
",RMQ_find(ll,rr));
        }
    }
 
    return 0;
}

View Code

　　2.线段树 O(n*logn)

如果有相关的题目，会继续更新