您好,UncleToo欢迎您!  为了更好的浏览本站,请使用高版本浏览器
RSS  Tag     设为首页 | 加入收藏
 您所在的位置:首页 > 互联网大小事 > 职场风云

QQ空间部门面试Web前端的算法题

作者:  来源:互联网  日期:2013-10-31 20:58:44
收藏  评论:( 0 )  阅读:700

题目是:有一组数字,从1到n,从中减少了3个数,顺序也被打乱,放在一个n-3的数组里<br>请找出丢失的数字,最好能有程序,最好算法比较快。
作者是解决方法是:

var n=10;
function test(){
        var a=[3,7,10,1,4,5,8];
        var b=[1,2,3,4,5,6,7,8,9,10];
        for(var i=0,c=a.length;i&lt;c;i++){
                delete b[a[i]-1];
        }
        b.sort();
        var len=b.length-a.length;
        for(var i=0;i&lt;len;i++){
                document.write(b[i]+"");
        }
}
test();

作者假设了一个前提是:源数组中的数据都是1-n个数字,但是,举一反三的话,如果数据与对应的索引值存在某种可计算的关系的话,也可以用该算法,确实效率很高!我想的是如果数组中的数据与索引之间没有联系,那么我们该怎么办呢?当然可以一遍一遍地遍历,那么时间为O(n1*n2),但是如果采用java中hash表的思想来做的话,那么时间为O(max(n1,n2)),因为在这里只是简单的无重复的数据,如果知道数据的特点,可以构造相应的hash表来处理。下面是源代码:

//在arr1数组中查找arr2数组中的值,假设arr1和arr2数组中值都为正整数
function test(arr1,arr2){
        var keyArr=new Array();
        var valueArr=new Array();
        for(var i=0;i&lt;100;i++){
                keyArr[i]=-1;
        }
        //构造hash表,构造的hash码公式为key=value;
        for(var i=0;i&lt;arr2.length;i++){
                keyArr[arr2[i]]=i;
        }
        //在arr1中查找对应的值
        for(var i=0;i&lt;arr1.length;i++){
                var key=arr1[i];
                if(keyArr[key]==-1){
                        valueArr.push(arr1[i]);
                }
        }
        return valueArr;
}
//测试
var test1=[11,22,24,56,34,77];
var test2=[11,22,56];
alert(test(test1,test2));




QQ
 
面试
 
算法
 
除非特别声明,本站所有PHP教程及其他教程/文章均为原创、翻译或网友投稿,版权均归UncleToo中文网所有, 转载请注明作者及出处。
原文网址:http://www.uncletoo.com/html/jobs/502.html
读完这篇文章后,你是否有所收获? 分享是一种生活的信念!
  • 0
  • 0
我来说两句
更多>>网友评论