1

伙计们，我需要你的意见；我之前在面试中遇到过这个问题，我只是想确认我理解了这个问题并且我得到了正确的答案。谢谢你。请检查下面的问题和我的答案：

取一个输入一维数组[1,2,3,4]，输出不包括当前索引[24,12,8,6]的整数的乘积；

//My answer
function calculate(values:Array):Array {
    var resultArray:Array = new Array();
    for(var i:int = 0; i < values.length; i++) {
        var getVal1:Number = 1;
        for(var k:int = 0; k <= values.length; k++) {
            if(i != k) {
                var getVal2:Number = values[k];
                getVal1 *= getVal2;
            }
        }
        resultArray.push(getVal1);
    }
    return resultArray;
}
4

5 回答 5

4

嵌套循环似乎是一种非常混乱的方式。

假设相对最新的浏览器（IE 8 及以下版本已出）或合适的 shim：

var resultArray = sourceArray.map(function(val,ind,arr) {
    arr = arr.slice(0); // create copy of array to work on here
    arr.splice(ind,1); // remove current item from array
    return arr.reduce(function(prev,curr) {return prev*curr;},1);
});

Array.prototype.map
Array.prototype.reduce

编辑这是另一种更有效的方法：

var product = sourceArray.reduce(function(prev,curr) {return prev*curr;},1);
var resultArray = sourceArray.map(function(val) {return product/val;});
于 2013-06-25T23:48:31.353 回答
2

您的解决方案给出了正确的答案，但有一种更有效的方法来计算新数组：

function calculate(values:Array):Array {
    var resultArray:Array = new Array();
    var product:int = 1; 

    for(var i:int = 0; i < values.length; i++) {
        product *= values[i];
    }

    for(var i:int = 0; i < values.length; i++) {
        resultArray.push(product / values[i]);
    }

    return resultArray;
}

此解决方案具有O(n)执行时间，而您的代码具有O(n²)执行时间。

于 2013-06-25T23:49:00.087 回答
1

那应该行得通。您可以通过首先将所有项目相乘来更轻松、更有效地完成此操作：

function calculate(values) {
  var prod = 1;
  for (var i = 0; i < values.length; i++) prod *= values[i];
  var result = [];
  for (i = 0; i < values.length; i++) result.push(prod / values[i]);
  return result;
}
于 2013-06-25T23:51:45.770 回答
0

我相信我下面的代码很容易阅读。并且没有嵌套循环，而是两个连续的。我的回答是：

function calculate(array){
    var total = array.reduce(function(a, b){
        return a * b;
    });

    return array.map(function(element){
        return total / element;
    });
}
于 2013-06-25T23:58:49.880 回答
0

虽然我最喜欢@Kolink 的短而高效的解决方案，但这是解决任务的另一种方法 - 不使用除法但仍在O(n)：

function calculate(values) {
    var acc = 1,
        l = values.length,
        result = new Array(l);
    for (var i=0; i<l; i++) {
        result[i] = acc;
        acc *= values[i];
    }
    acc = 1;
    while(i--) {
        result[i] *= acc;
        acc *= values[i]
    }
    return result;
}

或者，同样的事情，但有点混淆*：

function calculate(values) {
    var acc = 1,
        i = 0,
        l = values.length,
        result = new Array(l);
    if (l)
        result[i] = 1;
    while( ++i < l)
        result[i] = acc *= values[i-1];
    i -= acc = 1;
    while (i--)
        result[i] *= acc *= values[i+1];
    return result;
}

*：我喜欢速记运算符！

于 2013-06-26T00:03:03.117 回答