0

有人可以调试这段代码吗？我一生都找不到（运行时）错误：

function generate_fibonacci(n1, n2, max, out){
    var n = n1+n2;
    if(n<max){
        out.push(n);
        generate_fibonacci(n2, n, max, out);
    }
}

function generate_fibonacci_sequence(max){
    var out = [1];
    generate_fibonacci(0, 1, max, out);
    return out;
}

function remove_odd_numbers(arr){
    for (var i = 0; i < arr.length; i++) {
        if(!(arr[i]%2==0)){
            arr.splice(i, 1);
        }
    }
    return arr;
}

function sum(array){
    var total = 0;
    for (var i = 0; i < array.length; i++) {
        total+=array[i];
    }
    return total;
}

var fib_sq = generate_fibonacci_sequence(4000000);

console.log("Before: " + fib_sq);

remove_odd_numbers(fib_sq);

console.log("After: " + fib_sq);

console.log("WTH?: " + remove_odd_numbers([1,2,3,4,5,6,7,8,9]));

输出：

Before: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578
After: 1,2,5,8,21,34,89,144,377,610,1597,2584,6765,10946,28657,46368,121393,196418,514229,832040,2178309,3524578
WTH?: 2,4,6,8
[Finished in 0.3s]

我要疯了还是怎么的。由于某种原因，所有奇数都没有被删除。但正如您在最后看到的那样，它运行良好。我不知道发生了什么。

4

5 回答 5

8

原始代码中的问题是，当您删除1索引 0 处的第一个时，数组会移动；现在 arr[i]是包含第二个1；但你只是跨过它。

您需要在此处使用 while 而不是 if，或复制到单独的列表中。这是一个拼接的例子：

function remove_odd_numbers1(arr){
    for (var i = 0; i < arr.length; i++) {
        // here
        while (arr[i] % 2) {
            arr.splice(i, 1);
        }
    }
    return arr;
}

但它会很慢。最好创建一个新数组：

function remove_odd_numbers2(arr){
    var rv = [];
    for (var i = 0; i < arr.length; i++) {
        if (! (arr[i] % 2)) {
            rv.push(arr[i]);
        }
    }
    return rv;
}

但是，通常最好的算法是使用相同的数组，如果不需要原始数组，则不需要额外的内存（尽管在 javascript 上这有点可疑）：

function remove_odd_numbers3(arr){
    var out = 0; 
    for (var i = 0; i < arr.length; i++) {
        if (! (arr[i] % 2)) {
            arr[out++] = arr[i]; 
        }
    }
    arr.length = out;
    return arr;
}

但是请注意，与拼接算法不同，它是O(n)及时运行的。

此外， Array.prototype.filter() 也不错，是内置的。它还创建了一个新数组，因此与 2 相当。

于 2013-08-19T01:56:00.027 回答
2

我不确定这一点，但是我怀疑使用splice与创建新数组相比是否有效。

function remove_odd_numbers(arr) {
    var notOdd = [],
        i = 0,
        len = arr.length,
        num;

    for (; i < len; i++) {
        !((num = arr[i]) % 2) && notOdd.push(num);
    }

    return notOdd;
}

编辑：您可能应该filter按照@Jack 的建议使用本机功能。我将此答案作为参考。

于 2013-08-19T02:04:50.020 回答
2

这是一个非常简单、快速的方法。使用您的数据，只需 48 毫秒即可完成。希望这可以帮助..

function noOdds(values){
  return values.filter(function (num) {
    return num % 2 === 0;
  });
}
于 2015-06-19T18:38:10.067 回答
1

因为splice()修改了数组，你的索引将在下一次迭代中关闭；您需要减少循环变量，使用while像 Antti提出的循环或像 Crazy Train提到的那样向后迭代。

也就是说，使用 ofsplice()很尴尬，因为它会就地修改数组。使用过滤器功能也可以轻松实现此功能：

function remove_odd_numbers(arr) 
{
    return arr.filter(function(value) {
        return value % 2 == 0;
    });
}

这将创建并返回一个只有偶数值的新数组。

鉴于此功能的新近，请查看兼容性部分如何处理 IE < 9 的浏览器。许多流行的库，例如 jQuery、下划线等，都会为您处理这个问题。

更新

与其在之后过滤数组，不如在执行递归时仅添加偶数值会更节省内存：

function generate_fibonacci(previous, current, max, callback)
{
    var next = previous + current;

    if (next < max) {
        callback(next);
        generate_fibonacci(current, next, max, callback);
    }
}

function generate_fibonacci_sequence(max, callback)
{
    callback(1);
    callback(1);
    generate_fibonacci(1, 1, max, callback);
}

var out = [];
generate_fibonacci_sequence(4000000, function(value) {
    if (value % 2 == 0) {
        out.push(value);
    }
});

我没有传递数组，而是传递了out一个在生成新序列值时调用的函数；过滤是在该回调中完成的。

于 2013-08-19T02:01:38.630 回答
1

来自“Tabetha Moe”答案的 ES6 版本

function noOdds(arr) {
    return arr.filter(value => value % 2 === 0);
}
于 2018-04-19T09:37:32.530 回答