两个嵌套的for/循环，没有重复的对

Two nested for/loops without duplicated pairs

本文关键字：循环 for 两个 嵌套      更新时间：2023-09-26

我们有数组：

var arr = [0,1,2];

和环路：

for ( var i=0; i<arr.length; i++ ) {
    for ( var j=0; j<arr.length; j++ ) {
        if ( arr[i] == arr[j] ) continue;
        console.log(arr[i], arr[j]);
    }
}

输出：

0,1 //a--|
0,2 //b--|--|
1,0 //a--|  |
1,2 //c-----|--|
2,0 //b-----|  |
2,1 //c--------|

正如我们所看到的，存在重复的对(在注释a、b和c中出现两次(

我们能够消除重复对的唯一方法是将已经"匹配"的对存储在某种内存中？

var mem = {};
for ( var i=0; i<arr.length; i++ ) {
    for ( var j=0; j<arr.length; j++ ) {
        var left = i;
        var right = j;
        if ( left > right ) {
            var temp = right;
            right = left;
            left = temp;
        }
        if ( arr[i] == arr[j] || mem[arr[left]+","+arr[right]] ) continue;
        console.log(arr[i], arr[j]);
        mem[arr[left]+","+arr[right]] = true;
    }
}

输出：

0,1
0,2
1,2

但这需要额外的内存(对于更大的阵列，它需要很多内存。(

有没有其他方法可以不存储任何额外的东西？

如果你的输入数组是唯一的，为什么不从i+1 开始你的j呢

for ( var i=0; i<arr.length; i++ ) {
    for ( var j= i + 1 ; j<arr.length; j++ ) {
        console.log(arr[i], arr[j]);
    }
}

一种可能的算法如下：

  1. 对数组进行排序。

  2. 从数组中删除重复的值(保留1(，对于每个有重复的值x，输出(x,x)。

  3. 对于每对索引i和j使得i < j，输出对应的对(i,j)。

虽然这可能不会产生排序的输出，但它确实处理了重复的值和未排序的输入数组。

for ( var i=0; i<arr.length; i++ ) {
    for ( var j=0; j<arr.length; j++ ) {
        if ( arr[i] == arr[j] || j<i) continue;
        console.log(arr[i], arr[j]);
    }
}

这应该行得通。

说明：如果j小于i，则可以切换i和j以获得具有相同两个值的另一个输出。但是，如果在数组中使j"领先"于i，则不会输出重复项。

如何"看起来"：

o=阵列值

x=arr[i]

|=arr[j]

-=arr[i]和arr[j]都在这个点

-oooo//继续

x|ooo

xo|oo

xoo|oxooo|

然后，没有变化：

|xooo//输出！与行(/step(2相同！

o-ooo//继续

ox|oo

随着变化：|xooo//j在i之前，所以不要输出。避免重复行(/步骤(2。

o-ooo//继续

ox|oo

等等。

相关文章：