2

我有两个排序数组。我需要找出两者是否不同。

这些数组具有特定范围内的元素。

不止一个元素可能不同。

数组可以有不同的大小。在这种情况下，我应该能够指出差异

一个粗略的例子：

输入：

array1: 1 2 4 5 8 9 12
array2: 1 4 8 10 12 13 14

这里的范围是 1-15。

什么是最优化的比较算法？

我也应该能够指出差异和相似之处，例如，两个数组中都有 4，而第二个数组中缺少 5。

我的解决方案：

  1. 两个指针来跟踪数组的索引。

  2. 将它们指向数组的开头。

  3. 开始比较前两个元素。

  4. 如果两者相等--> 移动到下一个。
    别的

    1. 找到数组的两个元素中的最大值。说 array1 有更大的元素。

    2. 对另一个数组中的元素进行二进制搜索。(array2) --> 该数组中该元素的 pos 说 pos

    3. 丢弃数组的元素直到 pos。

  5. 增量指针。丢弃数组的那部分直到这个指针。重复。

这具有n log n（远低于平均水平，这是您必须搜索每个元素的时候）的复杂性。

4

7 回答 7

2

(4.) - 代替二分搜索做线性搜索。

总体复杂性：O(n) - 因为您只访问每个项目一次。

于 2013-08-21T08:19:06.323 回答
1

完全未经测试（当有重复时效果不佳）：

var same = new List<int>();
var inAonly = new List<int>();
var inBonly = new List<int>();

int b = 0;
int a = 0;
//first look at all the elements until one of the lists run out of elements
for(; a < inputa.Count && b < inputb.Count;) {
     //if element is the same, then add to same
     //and the problem with duplicates is found here, if a contains two "1", but b only contains one, then same will report a single "1", but inAonly will also contain a "1"
     if (inputa[a] == inputb[b]){
       same.Add(inputa[a]);
       a++;
       b++;
     }
     //otherwise, we check if a < b, if that is the case, we know that a only exists in a, otherwise it must only exist in b.
     else if (inputa[a] < inputb[b])
     {
        inAonly.Add(inputa[a]);
        a++
     } else         {
        inBonly.Add(inputb[b]);
        b++
     }
}
//add the rest of the elements if one array is longer than the other
for(; a < inputa.Count;a++)
   inAonly.Add(inputa[a]);
for(; b < inputb.Count;b++)
   inBonly.Add(inputb[b]);
于 2013-08-21T08:40:48.430 回答
0

如果 array1 和 array2 具有相同的大小，则遍历它们并逐个元素地比较它们。当找到第一个差异时=>数组不同。如果到达数组的末尾，则表示它们相等。复杂性是时间上的 O(array's length) 和内存中的 O(1)。

如果 array1 和 array2 具有不同的大小，则分配另一个具有大小的数组 - 元素的范围，并用零 (array3) 对其进行初始化。对于 array1 中的每个元素，array3 中的增量元素如下所示：array3[array1[i]]++

之后以相同的方式迭代array2，但递减：array3[array2[i]]--

之后，对于 array3 中的每个元素，您有 3 种可能性：

  • if array3[i] == 1 //那么元素 i 在 array1 但不在 array2
  • if array3[i] == -1 //那么元素 i 在 array2 但不在 array1
  • if array3[i] ==0 //那么元素 i 在两个数组中或都不在其中。

时间复杂度 - O(range)，内存复杂度 - O(range)。如果范围不是从 0 开始，那么您可以为每个索引设置一个偏移量。

例子：

  • 范围：1-15
  • 数组1：1 2 4 5 8 9 12
  • 数组2：1 4 8 10 12 13 14

step1 之后，array3 将如下所示：

index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

value: 1 1 0 1 1 0 0 1 1  0  0  1  0  0  0

在 step2 之后 array3 将如下所示：

index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

value: 0 1 0 0 1 0 0 0 1 -1  0  0 -1 -1  0
于 2013-08-21T09:06:36.753 回答
0

@Alvin您的算法似乎适合我。由于您必须指出相似之处和不同之处，因此您必须进行搜索以防万一。

我认为复杂性会比 nlgn 更好，因为您不必在完整的数组中搜索每个差异。这是因为您也将元素丢弃到 pos 。

于 2013-08-21T08:59:42.173 回答
0

您在处理此问题的方式上处于正确的轨道上，但是没有必要进行搜索。（实际算法见底部）

从 2 个指向开头的指针开始：

        v
array1: 1 2 4 5 8 9 12

        v
array2: 1 4 8 10 12 13 14

（就像您一样）如果元素相同，请将它们添加到您的"In-Both"设置中，然后增加两个指针，所以现在我们有：

          v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

所以现在我们遇到了不同的元素，而不是在这里搜索，我们可以利用这样一个事实，即我们知道指针所在的位置不可能有 2，array2所以我们添加2到我们的"Only_in_array1"集合中。并且只增加array1指针。所以我们最终得到：

            v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

我们以匹配结束，所以我们将 4 添加到"In-Both"并增加两个指针：

              v
array1: 1 2 4 5 8 9 12

            v
array2: 1 4 8 10 12 13 14

如果你继续这种模式，你最终会得到：

                     v
array1: 1 2 4 5 8 9 12

                  v
array2: 1 4 8 10 12 13 14

当第一个指针从数组中掉出来时，你会知道第二个（更长的）数组中的其余元素不在第一个。

泛化算法：

  • 从两个数组开头的 2 个指针开始（以及您想要保存信息的初始化和数据结构：我使用了 3 个列表/集合）

  • 您现在可以拥有三种情况之一

    1. p1 的值等于 p2：将值添加到in both数组并同时递增

    2. p1 的值小于 p2：将 p1 的值添加到only in array1数组中并仅增加 p1

    3. p1 的值大于 p2：将 p2 的值添加到only in array2数组中并仅增加 p2

  • 在这些条件上循环，直到到达数组的一个（或两者，如果它以这种方式发生）的末尾。然后将另一个列表中的任何剩余项目添加到其各自的only in arrayX列表中。

该算法只命中每个项目一次，因此它应该是 O( n )。希望这可以帮助

于 2013-08-21T13:28:39.120 回答
0

因为两个数组都是排序的。最好是使用线性搜索。

于 2013-08-21T08:20:54.237 回答
0

如果数组是内存块——你可能已经用 malloc 分配了一些东西，你可以通过将数组转换为 32 位或 64 位整数来加速比较。这样，您就可以将多个数组元素与单个 == 测试进行比较。

此外，如果您知道数组具有特定数量的元素，那么将循环展开到例如 8 个 if 语句会更快。它将保存比较并在每次循环结束时跳转。

于 2013-08-21T08:22:26.590 回答