在数组中查找唯一对
在数组中查找唯一对
提问于 2019-04-03 17:48:20
有了这个输入[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来改进排序/映射，但我的问题更多的是关于算法的改进。
回答 2
Stack Overflow用户
回答已采纳
发布于 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; }
Stack Overflow用户
发布于 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%
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55492102
复制相关文章
相似问题