互联网公司面试题之九

YuHuang.Neil

问题一：查找一个数组中的第K小的数，注意同样大小算一样大。如2 1 3 4 5 2，第三小数为3。
时间复杂度要求达到O(n)。

答：实现代码如下（位图算法实现）：
s,m,j;main(i,n){   char a[65535]={0,};   for(;~scanf("%d",&n);printf("%d\n",--i-32768)){     for(i=0;i<n;++i) {scanf("%d",&s);a[s+32768]=1;}            scanf("%d",&m);     for(i=0;i<65535&&m;++i) if(a) --m;     for(j=0;j<65535;++j) a[j]=0;   }}

运行结果：
10个数，找出第二小数





问题二：输入一个N（1<=N<=100）维矩阵，判断是否对称。

答：实现代码如下：
main(i,n){   for(;~scanf("%d",&n);)   {        for(i=0;i<n;++i)           for(j=0;j<n;++j) scanf("%d",&a[j]);        m=0;        for(i=1;i<n;++i){           j=1;           while(i-j>=0)            if(a[i-j]==a[i-j]) ++j;           else {m=1;goto OUT;}        }                            OUT:  printf("%s\n",m==0?"Yes!":"No!");   }       }

运行结果：