arrays - 在多个数组中查找序列号的有效方法？

Question

我不是在寻找任何代码或为我做任何事情。我需要一些帮助才能朝着正确的方向开始，但不知道如何去做。如果有人可以提供一些有关如何解决这些问题的资源，我将不胜感激。我一直坐在我的笔记本电脑前，但在设计一种可以完成我想做的事情的算法时遇到了麻烦。

我可能会做:

foreach element in array1
    foreach element in array2
        check if array1[i] == array2[j]+x

我相信这对前向和后向序列都有效，对于倍数，只需检查 array1[i] % array2[j] == 0。我有一个包含 int 数组的列表，并且正在获取 list[index](对于 array1)和 list[index+1] 对于 array2，但此解决方案可能会很快变得复杂和冗长，尤其是对于大型数组和这些数组的大量列表。因此，我正在寻找更好的解决方案。


我正在尝试想出一种算法来查找不同数组中的序号。

例如:

[1, 5, 7] 和 [9, 2, 11] 会发现 1 和 2 是连续的。

这也适用于多个数组中的多个序列。因此，如果存在 [24, 3, 15] 的第三个数组，它也会在该序列中包含 3，并继续到下一个数组，直到没有t 匹配 last sequential element + 1 的数字。

它还应该能够在数组之间找到一个以上的序列。

例如:

[1, 5, 7] 和 [6, 3, 8] 会发现 5 和 6 是连续的，7 和 8 也是连续的。

我也有兴趣寻找反向序列。

例如:[1, 5, 7] 和 [9, 4, 11] 将返回 5 而 4 是相反的顺序。

全部示例:

[1, 5, 8, 11] 和 [2, 6, 7, 10] 将返回 1 和 2是顺序的，5和6是顺序的，8和7是逆序的，11 和 10 是逆序的。

它也可以重叠:

[1, 5, 7, 9] 和 [2, 6, 11, 13] 将返回 1 和 2 顺序，5 和 6 顺序以及 7 和 6 反向顺序。

我还想扩展它以检查差异为 x 的数字(以上示例检查差异为 1)。

除了所有这些(虽然这可能是一个不同的问题)，我还想检查倍数，

例子:[5, 7, 9] 和 [10, 27, 8] 将返回 5 和 10 作为倍数, 9 和 27 作为倍数。

和相同位置的数字。

例子:[3, 5, 7] 和 [13, 23, 25] 将返回 3 和 13 和 23 有相同的个位。

Answer 1

使用字典(set 或 hashmap)

dictionary1 = {}

遍历第一个数组中的每个项目并将其添加到字典中。[1, 5, 7]

现在 dictionary1 = {1:true, 5:true, 7:true}

dictionary2 = {}

现在遍历 [6, 3, 8] 中的每个项目并查找它是否是序列的一部分。

6 是序列的一部分，因为 dictionary1[6+1] == true所以 dictionary2[6] = true

我们得到 dictionary2 = {6:true, 8:true}

现在设置 dictionary1 = dictionary2 和 dictionary2 = {}，然后转到第三个数组..等等。

我们只跟踪序列。由于每次查找都是 O(1)，并且我们对每个数字进行 2 次查找(例如 6-1 和 6+1)，因此总数为 n*O(1)，即 O(N)(N 是数字的数量跨所有阵列)。