java - 查找两个数组之间的差异

Question

这看起来不像是现有交集/并集问题的重复(我可能错了)。

我有两个 ArrayList，其中包含一个包含值的类，例如

class A {
    private int value;

    public int getValue() {
        return value;
    }
}

我的列表是

ArrayList<A> first, second;

我想从 first 和 second 中找到两个索引，其中第一个索引指向 first 中的项，相应的值仅在first 但不在 second 中，其他索引是 second 中的索引，相应的值仅在 second 中，但不在第一个。

例如(从中心行读取数据):

hit                  *   *
index of first   0   1   2   3
----------------------------------
first.value      1   3   5   7
second.value     1 2   4   6 7 8
----------------------------------
index of second  0 1   2   3 4 5
hit                *   *   *   *

我想要两个索引 1 2 和 1 2 3 5。

注意:

1. 我不想使用第三方库
2. 值是整数并已排序，并且返回也必须按顺序。
3. first 和 second 的长度不确定 - 任何一个都可以比另一个长。

谢谢。

PS:任何人都需要更多细节，这是我的问题的简化版本。 first实际上是一个SQL查询的ResultSet，它是服务器上的所有记录，second是本地记录的列表(或者考虑从另一个本地数据库处理)，我想要做的是删除服务器上(第一个)不包含在本地数据库(第二个)中的所有记录，并将这些缺失的记录添加到远程数据库中。谢谢。

<小时/>

致@Tibrogargan

我的目标是将本地数据库(sqlite)增量传输到远程数据库(MySQL)。本地数据库有一个名为 LocalId 的字段(没有重复且不是主键)，当然还有其他内容(约 10 个字段)，除了将所需字段(约 5 个字段)复制到远程数据库之外，我还添加了一个字段来确定是否从本地数据库中删除该记录。

作为其他要求，我已经将所有本地数据读取到 ArrayList 中，在本地数据库上按 LocalId 排序，并可以通过 访问所有远程数据rs，按远程数据库上的LocalId排序。

我早期版本的代码是在本地数据库上查找最后一个 LocalId，并标记远程数据库上 LocalId 大于最大 的所有记录本地数据库上的 LocalId。然而，直到我发现我并不总是删除本地数据库上的尾部记录，所以我发现有必要迭代所有消息并比较是否存在。

我不知道是否有任何“更好”的解决方案，但似乎如果我将所有本地消息加载到远程，性能会很糟糕？

哦，只需提一下，远程和本地数据集上都存在数百到 100+k 条记录，而只有数十条消息需要删除并添加到远程。确定远程记录是否应标记为已删除的逻辑取决于本地数据集上是否存在相应消息(相同的 LocalId)。

Answer 1

由于数组已排序，因此您可以循环遍历它们，并随时检查是否有重复项。这是一些伪代码:

//loop over both arrays at once
int arrayAIndex = 0;
int arrayBIndex = 0;
while (arrayAIndex < arrayA.length && arrayBIndex < arrayB.length) {
  if (arrayA[arrayAIndex] == arrayB[arrayBIndex]) {
    arrayAIndex++;
    arrayBIndex++;
  } else if (arrayA[arrayAIndex] > arrayB[arrayBIndex]) {
    addToResultB(arrayBIndex);
    arrayBIndex++;
  } else if (arrayB[arrayBIndex] > arrayA[arrayAIndex]) {
    addToResultA(arrayAIndex);
    arrayAIndex++;
  }
}

//clean up any elements which were not looked at during the above
while (arrayAIndex < arrayA.length) {
  addToResultA(arrayAIndex);
  arrayAIndex++;
}
while (arrayBIndex < arrayB.length) {
  addToResultB(arrayBIndex);
  arrayBIndex++;
}