互联网公司面试题之九
问题一：查找一个数组中的第K小的数，注意同样大小算一样大。如2 1 3 4 5 2，第三小数为3。时间复杂度要求达到O(n)。
答：实现代码如下（位图算法实现）：
s,m,j;main(i,n){ char a={0,}; for(;~scanf("%d",&n);printf("%d\n",--i-32768)){ for(i=0;i<n;++i) {scanf("%d",&s);a=1;} scanf("%d",&m); for(i=0;i<65535&&m;++i) if(a) --m; for(j=0;j<65535;++j) a=0; }}
运行结果：
10个数，找出第二小数
http://dl.iteye.com/upload/attachment/606784/ba1e0fcd-6fab-3731-8648-196244e61c0b.jpg
问题二：输入一个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); m=0; for(i=1;i<n;++i){ j=1; while(i-j>=0) if(a==a) ++j; else {m=1;goto OUT;} } OUT:printf("%s\n",m==0?"Yes!":"No!"); } }
运行结果：
http://dl.iteye.com/upload/attachment/607055/f22bebe7-32dc-3a57-b5dc-63aaf2768249.jpg
页:
[1]