java - 将两个集合(有重复项)合并为一个集合(无重复项)

Question

我在多个客户端上同步数据时遇到问题。为简单起见，假设我有两个可能重复的集合(名称 是关键):

"collection1": [
    {
    "name": "a",
    "timestamp": 1
  },
    {
    "name": "a",
    "timestamp": 2
  },
    {
    "name": "b",
    "timestamp": 1
  }]

   "collection2": [
    {
    "name": "a",
    "timestamp": 3
  },
    {
    "name": "c",
    "timestamp": 2
  }]

我想要没有重复的集合(name 是关键)，具有最高的时间戳值。所以合并后它应该是这样的:

"collection3": [
     {
    "name": "b",
    "timestamp": 1
  },
    {
    "name": "a",
    "timestamp": 3
  },
    {
    "name": "c",
    "timestamp": 2
  }]

顺便说一句。我不在乎秩序。我不能只是简单地Set = new HashSet<>(collectionn);因为缺少替换过载。

我的想法是做3次removeDuplication

1. collection1 与 collection1
2. collection2 与 collection2
3. 集合 1 和集合 2

使用这个 O(n^2) 的 removeDuplication 函数:

LinkedList<MyObject> finalList = new LinkedList<>();

    for (MyObject newObject : collection) {
        boolean foundSimillar = false;
        for (MyObject objectAlreadyAdded : finalList) {
            if (Objects.equals(newObject, objectAlreadyAdded)) { // in this case if(name1 == name2)
                foundSimillar = true;
                long newObjectTime = newObject.lastTimeModified;
                long alreadyAddedObjectTime = objectAlreadyAdded.lastTimeModified;
                if (newObjectTime > alreadyAddedObjectTime) {
                    finalList.remove(objectAlreadyAdded);
                    finalList.add(newObject);
                    break;
                }
            }
        }
        if(!foundSimillar)
            finalList.add(newObject);
    }

有没有比我的 3 * O(n^2) 更高效的算法？

Answer 1

您应该能够使用 Map 执行此操作。您只需检查键是否在映射中(如果 newValue > oldValue 则更新值)，否则您移动到下一个元素。

总的时间复杂度应该是O(N)

一旦所有插入完成，您可以通过一次迭代重建您的 json。