获取数组 Javascript 的所有整数组合的另一种方法

Another way to get all combination of integers of an array Javascript

本文关键字：组合 另一种 方法 整数 数组 Javascript 获取      更新时间：2023-09-26

我想迭代一个数组并找到所有相差为 2 的对

这是我到目前为止所拥有的：

var numberOfCases = 5;
var diff = 2;
var input = [1,5,3,4,2];
getPossiblepairs(input);
function getPossiblepairs(input){
    for(cmp in input){
        for(number in input){
            if((input[cmp] - input[number]) == diff){
                console.log("("+input[cmp]+","+input[number]+")");
            }
        }
    }
}

这有效，但我仍然对使用两个 for 循环感到内疚，因为 bigO 是 O（n^2） 这是唯一的方法吗？

你可以在 O（n log n） 中执行此操作。对数组进行排序，然后在一次传递中遍历它。找到当前元素与接下来两个元素之间的差异，如果一个元素相差 2，则打印出该对。

这应该适用于 n log n 复杂性：

function getPossiblepairs(input, diff){
    // Create a copy of the original array, so it is not affected by the next operation
    var sortedInput = input.slice();
    // Sort the array
    sortedInput.sort();
    // Iterate through the array, starting from the 0th element
    for (var i=0, n=sortedInput.length; i<n; i++){
        firstNumber = sortedInput[i];
        // Iterate through the array, starting from the (i+1)th element
        for (var j=i+1; j<n && sortedInput[j] <= firstNumber + diff; j++){
            secondNumber = sortedInput[j];
            // if it matches, then log it!
            if (secondNumber - firstNumber == diff){
                console.log('(' + firstNumber + ', ' + secondNumber + ')');
            }
        }
    }
}

有关阵列复制的更多信息，请参阅此文章。

有关用法和测试，请参阅：http://jsfiddle.net/gycjup5u/2/

你有内存来存储数组的副本吗？ 首先对其进行排序，O（n log n），然后在单个 O（n） 传递中挑选出对。

您可以对每个元素使用 indexOf() 方法来确定数组是否包含大于 diff 给出的元素：

function getPossiblePairs(input, diff) {
    for(i in input) {
        var n = input.indexOf(input[i] + diff);
        if(n != -1) {
            console.log("(" + input[i] + "," + input[n] + ")");
        }
    }
}
getPossiblePairs(input, diff);
相关文章：