没有重复对的两个嵌套 for/loops
Two nested for/loops without duplicated pairs
我们有数组:
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 出现了两次)
我们摆脱重复对的唯一方法是将已经 "matched" 对存储在某种内存中?
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),对于每个有重复的值 x
,输出 (x,x)
.
对于每一对索引 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"ahead" of i,那么就不会输出重复的。
如何 "looks":
o=数组值
x=arr[i]
|=arr[j]
-=arr[i]和arr[j]都在这个地方
-oooo //继续
x|ooo
xo|oo
xoo|o
xoo|
然后,没有变化:
|xooo //输出了!与第 2 行(/步骤)相同!
o-ooo //继续
牛|oo
随着变化:
|xooo //j在i之前,所以不输出。避免重复行(/step) 2.
o-ooo //继续
牛|oo
等
我们有数组:
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 出现了两次)
我们摆脱重复对的唯一方法是将已经 "matched" 对存储在某种内存中?
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),对于每个有重复的值
x
,输出(x,x)
.对于每一对索引
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"ahead" of i,那么就不会输出重复的。
如何 "looks":
o=数组值
x=arr[i]
|=arr[j]
-=arr[i]和arr[j]都在这个地方
-oooo //继续
x|ooo
xo|oo
xoo|o xoo|
然后,没有变化:
|xooo //输出了!与第 2 行(/步骤)相同!
o-ooo //继续
牛|oo
随着变化: |xooo //j在i之前,所以不输出。避免重复行(/step) 2.
o-ooo //继续
牛|oo
等