我正在练习算法,正在做一个问题,即给你一个数组,你想返回一个数组,其中包含除该索引处的数字之外所有其他数字的乘积。 所以 [1, 2, 3, 4] 将返回 [24, 12, 8, 6]。我的方法是遍历数组,制作副本,拼接当前索引,然后将该副本推送到输出数组。
function getAllProductsExceptAtIndex(arr) {
var productArr = [];
for (var i = 0; i < arr.length; i++) {
var copy = arr.slice();
copy.splice(i, 1);
productArr[i] = copy;
}
// return productArr;
for (var j = 0; j < productArr.length; j++) {
reduce(productArr[j]);
}
}
getAllProductsExceptAtIndex([1, 2, 3]); ---> productArr = [[2,3],[1,3],[1,2]]
现在你有一个包含正确值的输出数组,它只需要通过乘法"减少"到一个值。 现在reduce是时髦的,但在这种情况下,我试图提高效率(时间方面(,因此循环数组和reduce将是o(n(平方,因为reduce在内部使用for循环。 我想写一个帮助程序来减少,但如果你在循环中调用它,它仍然是 o(n( 平方吗?
有什么更有效的方法可以将 productArr 的每个索引内的元素相乘,然后展平? 宁愿不要在解决方案中使用除法。
此解决方案从面试蛋糕转换为 JS。强烈推荐用于学习算法:https://www.interviewcake.com/
"为了找到除每个索引处的整数之外的所有整数的乘积,我们将贪婪地浏览两次列表。首先,我们在每个索引之前获取所有整数的乘积,然后我们向后获取每个索引之后所有整数的乘积。
当我们把每个索引前后的所有乘积相乘时,我们得到答案——除了每个索引处的整数之外的所有整数的乘积!
function productOfInts(arr){
var productOfAllExceptIndex = new Array(arr.length);
var productSoFar = 1;
for (var i = 0; i < arr.length; i++){
productOfAllExceptIndex[i] = productSoFar;
productSoFar *= arr[i];
}
productSoFar = 1;
i -= 1;
while (i >= 0){
productOfAllExceptIndex[i] *= productSoFar;
productSoFar *= arr[i];
i--;
}
return productOfAllExceptIndex;
}
其实很简单:
function getAllProductsExceptAtIndex(arr) {
var product = arr.reduce(function(prev, curr) { return prev * curr; });
return arr.map(function(v) { return product / v; });
}
console.log(getAllProductsExceptAtIndex([1, 2, 3, 4]));
计算整个数组的乘积,然后将每个值映射到 product / current_value
,这是数组其余部分的乘积。
如果你想要一个不使用除法的解决方案,你可以把reduce
放在map
内,忽略当前项目:
function getAllProductsExceptAtIndex(arr) {
return arr.map(function(v, i) {
return arr.reduce(function(prev, curr, j) {
return i != j ? prev * curr : prev;
});
});
}
console.log(getAllProductsExceptAtIndex([1, 2, 3, 4]));
最后,以使代码稍微复杂化为代价,我们可以在 O(n( 时间内完成:
function getAllProductsExceptAtIndex(arr) {
if(arr.length === 0)
return [];
var i, products = [1];
for(i = 0; i < arr.length - 1; i++) {
products.push(products[i] * arr[i]);
}
for(var t = 1; i >= 0; i--) {
products[i] *= t;
t *= arr[i];
}
return products;
}
console.log(getAllProductsExceptAtIndex([1, 2, 3, 4]));
在这里,我们在第一次传递中计算每个索引左侧的乘积,但我们使用先前的计算来执行此操作 (O(n((。然后我们向后做同样的事情,向右计算乘积并乘以我们之前计算的乘积。在边缘情况下插入了一个常数">1" - 0 项的"乘积"([0]
的左侧和 [length - 1]
的右侧(。
要了解为什么这样做,请考虑将左侧所有项目的产品复制到任何项目右侧所有项目的产品意味着什么。
对于数组/对象操作,您可以使用下划线或 lodashhttps://lodash.com
// _.map : Produces a new array of values by mapping each value in list through a transformation function (iteratee) http://underscorejs.org/#map
_.map([1,2,3], function(value, index, collection){
return _.without(collection, value)
}) // -> [[2,3],[1,3],[1,2]]
如果你喜欢这个库,检查也是.js和字符串.js