有了这个输入[3,1,2]
,我希望有这个输出[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 2 ], [ 2, 3 ], [ 3, 3 ] ]
它的唯一对([1,2] == [2,1]
)
目前,我已经做到了
const arr = [3,1,2];
const pairBuilder = (left, index, collection) =>
collection.slice(index).map(right => [left, right]);
const pairs = arr.sort().flatMap(pairBuilder);
console.log(pairs)
这段代码是功能性的,但我想知道是否有更好的方法(在性能方面)来实现这一点?我想过(使用chain
)使用lodash来改进排序/映射,但我的问题更多的是关于算法的改进。
发布于 2019-04-03 18:23:55
您可以使用具有function*
的Generator
,并对数组进行切片,以便仅获得唯一对。
function* getPairs(array, left) {
var i = 0;
while (i < array.length) {
if (left) yield [left, array[i]];
else yield* getPairs(array.slice(i), array[i]);
i++;
}
}
var array = [1, 2, 3];
console.log([...getPairs(array)]);
.as-console-wrapper { max-height: 100% !important; top: 0; }
一种经典的方法。
function getPairs(array) {
var i, j, result = [];
for (i = 0; i < array.length; i++) {
for (j = i; j < array.length; j++) {
result.push([array[i], array[j]]);
}
}
return result;
}
var array = [1, 2, 3];
console.log(getPairs(array));
.as-console-wrapper { max-height: 100% !important; top: 0; }
发布于 2019-04-03 22:45:38
这是一种幼稚而缓慢的方法。但我相信它比问题中被接受的答案和答案要快。它生成的新对象开销更小,需要的内存也更少。朴素算法不使用递归。所以不会面临递归限制(默认是50),而且我相信它仍然是可读和容易理解的
const inp = [3, 1,2];
function genPair(inp) {
const length = inp.length;
const sorted = inp.sort();
const result = [];
for (let i = 0; i < length; i++) {
for (let j = i; j < length; j++) {
result.push([sorted[i], sorted[j]]);
}
}
return result;
}
const r = genPair(inp);
console.log(r);
链接到js perf https://jsperf.com/find-dups/1 Accepted在IE11中慢60%,在Chrome中慢10%
https://stackoverflow.com/questions/55492102
复制相似问题