2

基于作为对不同（相似）问题的答案给出的这个逻辑，为了以 O(N) 时间复杂度删除数组中的重复数字，我在 C 中实现了该逻辑，如下所示。但是我的代码的结果没有返回唯一的数字。我尝试调试，但无法得到它背后的逻辑来解决这个问题。

int remove_repeat(int *a, int n)
{
    int i, k;

    k = 0;
    for (i = 1; i < n; i++)
    {
        if (a[k] != a[i]) 
        {
            a[k+1] = a[i];
            k++;            
        }
    }
    return (k+1);
}

main()
{
    int a[] = {1, 4, 1, 2, 3, 3, 3, 1, 5};
    int n;
    int i;

    n = remove_repeat(a, 9);

    for (i = 0; i < n; i++)
            printf("a[%d] = %d\n", i, a[i]);


}

1] 上述代码中删除重复项的错误。

2] 此问题的任何其他 O(N) 或 O(NlogN) 解决方案。它的逻辑？

4

7 回答 7

2
  1. 在 O(n log n) 时间内进行堆排序。
  2. 在 O(n) 时间内迭代，用标记值（例如INT_MAX）替换重​​复元素。
  3. 在 O(n log n) 中再次进行堆排序以提取重复元素。

仍然以 O(n log n) 为界。

于 2011-07-17T15:13:19.263 回答
1

您的代码似乎需要对输入进行排序。在测试时使用未排序的输入，您的代码不会删除所有重复项（仅相邻的）。

于 2011-07-17T15:14:26.683 回答
1

如果整数的数量预先知道并且小于您拥有的内存量，您可以获得 O(N) 解决方案:)。一次通过来确定您使用辅助存储所拥有的唯一整数，然后再通过一次以输出唯一值。

下面的代码是用 Java 编写的，但希望你能明白。

int[] removeRepeats(int[] a) {
    // Assume these are the integers between 0 and 1000
    Boolean[] v = new Boolean[1000]; // A lazy way of getting a tri-state var (false, true, null)

    for (int i=0;i<a.length;++i) {
       v[a[i]] = Boolean.TRUE;
    } 

    // v[i] = null => number not seen
    // v[i] = true => number seen

    int[] out = new int[a.length];
    int ptr = 0;
    for (int i=0;i<a.length;++i) {
        if (v[a[i]] != null && v[a[i]].equals(Boolean.TRUE)) {
            out[ptr++] = a[i];
            v[a[i]] = Boolean.FALSE;          
        }
    }

    // Out now doesn't contain duplicates, order is preserved and ptr represents how
    // many elements are set.
    return out;
}
于 2011-07-17T15:22:51.837 回答
1

您将需要两个循环，一个遍历源，一个检查目标数组中的每个项目。

你不会得到 O(N)。

[编辑] 您链接到的文章建议使用排序的 输出数组，这意味着在输出数组中搜索重复项可以是二进制搜索......这是 O(LogN)。

于 2011-07-17T15:11:54.827 回答
1

您的代码仅检查数组中的项目是否与其直接前任相同。

如果您的数组开始排序，那将起作用，因为特定数字的所有实例都是连续的。

如果您的数组一开始没有排序，那将不起作用，因为特定数字的实例可能不连续，因此您必须查看所有前面的数字以确定是否已经看到一个。

要在 O(N log N) 时间内完成这项工作，您可以对数组进行排序，然后使用您已经拥有的逻辑从排序的数组中删除重复项。显然，这仅在您可以重新排列数字时才有用。

如果您想保留原始顺序，您可以使用哈希表或位集之类的东西来跟踪一个数字是否已被看到，并且仅在/如果尚未看到每个数字时将其复制到输出。为此，我们更改您的当前：

if (a[k] != a[i])
    a[k+1] = a[i];

类似于：

if (!hash_find(hash_table, a[i])) { 
    hash_insert(hash_table, a[i]);
    a[k+1] = a[i];
}

如果您的数字都落在相当窄的范围内，或者您希望这些值很密集（即大多数值都存在），您可能希望使用位集而不是哈希表。这将只是一个位数组，设置为零或一以指示是否已看到特定数字。

另一方面，如果您比一般情况更关心复杂性的上限，则可以使用平衡的基于树的集合而不是哈希表。这通常会使用更多内存并运行更慢，但其预期复杂度和最坏情况复杂度基本相同 (O(N log N))。在最坏的情况下，典型的哈希表会从恒定复杂度退化为线性复杂度，这会将您的整体复杂度从 O(N) 更改为 O(N 2 )。

于 2011-07-17T15:48:57.250 回答
0

你的逻辑错了，所以代码也错了。在编码之前自己做你的逻辑。我建议使用修改堆排序的 O(NlnN) 方式。使用堆排序，我们从 a[i] 连接到 a[n]，找到最小值并将其替换为 a[i]，对吗？所以现在是修改，如果最小值与 a[i-1] 相同，则交换最小值和 a[n]，将数组项的数量减少 1。它应该以 O(NlnN) 的方式完成。

于 2011-07-17T15:21:17.780 回答
0

您的代码仅适用于特定情况。显然，您正在检查相邻的值，但重复值可能出现在数组中的任何位置。因此，这是完全错误的。

于 2011-07-17T17:20:30.643 回答