2

我有 2 个数组，其中包含对象，例如：

[{"Start": 1, "End": 2}, {"Start": 4, "End": 9}, {"Start": 12, "End": 16}, ... ]

我想在删除重复项的同时合并 2 个数组。目前，我正在执行以下操作：

array1.concat(array2);

然后我正在做一个嵌套$.each循环，但是随着我的数组越来越大，这需要O(n^2)时间来执行并且不可扩展。

我认为有一种更快的方法可以做到这一点，但是，我发现的所有示例都使用字符串或整数。

有什么推荐的算法或方法可以加快速度吗？

4

3 回答 3

2

该答案基于以下假设：顺序无关紧要，您可以从对象创建唯一键。

您将数组 a 中的所有 n 个条目复制到对象 c，创建一个唯一键，然后将数组 b 中的所有 m 个条目复制到该对象（这将自动消除重复项），您将完成O(n+m)：

var a = [{"Start": 1, "End": 2}, {"Start": 4, "End": 9}];
var b = [{"Start": 4, "End": 9}, {"Start": 3, "End": 12}];

var c = {};
a.forEach(function(el){c[el.Start+".."+el.End] = el});
b.forEach(function(el){c[el.Start+".."+el.End] = el});

console.log(c);
// yields: {"1..2":{"Start": 1, "End": 2},"4..9":{"Start": 4, "End": 9},"3..12":{"Start": 3, "End": 12}}

这个对象中的这个符号有点多余，但是你合并两个数组的速度非常快。也许这可以进一步改进。

于 2013-02-01T16:45:51.750 回答
1

首先对对象进行排序，从低到高。O(n log n)与快速排序。

然后，您可以制作修剪算法，该算法可以利用这种排序在一个循环中循环遍历两个数组O(2n)。

合并原始数组和修剪后的数组。

请记住，尽管 JavaScript 中的对象没有顺序，但您无法对它们进行排序。转换为数组，保留引用并对其进行排序。

于 2013-02-01T16:26:02.120 回答
0

我对 javascript 不太熟悉，所以不能 100% 确定这是可行的（不确定比较对象是否相等等的细微之处），但是在 java 或其他语言中，这样的事情可能会起作用：

  • 迭代第一个数组。
  • 对于每个元素存储到一个“计数器”哈希图中，其中键是对象，值是计数。

在第一次通过之后，你应该有类似的东西：

{{"Start": 1, "End": 2}:1, {"Start": 4, "End": 9}:1, {"Start": 12, "End": 16}:1, ... }
  • 然后，遍历第二个数组
  • 对于每个元素，在计数器 hashmap 中查找当前元素。
  • 如果计数器 hashmap 包含与当前元素匹配的键，则它是重复的
  • 否则，追加到第一个数组。

可能比必须先排序快一点（如果可以使用对象作为键，那就是）？

于 2013-02-01T16:36:54.017 回答