算法一入深似海，从此前端是路人

算法 • sea • 发表于 10 年前 • 最后回复来自 qq2850071112 • 7 年前

哈哈...
来占个位置.
老题一个:
有由1,2,3...n-1,n 个整数组成的无序序列，现在少了两个，求之？

共收到6条回复

guokai 10 年前 #1

题目不完整吧。

fakefish 10 年前 #2

mark

zdjray 10 年前 #3

和,平方和联立,O(N)

huiop368 10 年前 #4

var arr = [2,10,9,8,4,5,1,6],ret = new Array(11),len = arr.length,dd,aa = [];
for(var i = 0;i<len;i){
dd = arr[i];
ret[dd] = 1;
}
len = ret.length
for(var j = 0;j<len;j){
if(!ret[j]) aa.push(j);
}
aa.shift();
console.log(aa) // [3,7]

sea 10 年前 #5

比较好的算法是时间复杂度是o(n)，空间复杂度是o(1)的。有两个：1.3楼的方法。2.用异或性质解。
方法1的常数时间小，较优，个人实现如下：

var num=1e2,
    inputArray=[],
    deleted,
    i=num;
while(i){
    inputArray[i-1]=i;
    i--;
}
inputArray.sort(function(){
    return Math.random()-0.5;
});
deleted=inputArray.splice(0,2);

function sumAndSqirt(){
    var n=0,
        m=0,
        i=num-2,
        foundDelete=[];
    while(i--){
        n+=inputArray[i];
        m+=inputArray[i]*inputArray[i];
    }
    n=(1+num)*num/2-n;
    m=num*(num+1)*(2*num+1)/6-m;
    foundDelete.push((n+Math.sqrt(2*m-n*n))/2);
    foundDelete.push(n-foundDelete[0]);
}

sumAndSqirt();

感谢@guokai 给我们提供这么好的交流社区，及开源代码供学习。

sea 10 年前 #6

@huiop368 建议不这么写ret = new Array(11);
考虑ret = new Array(11);和ret = new Array(11,22);
ret=new Array(11)有时可能会让人误解，推荐用字面量ret=[];

登录后即可参与回复

登录注册