删除到目前为止的重复数字删除下一个数字 Big O(n)

Question

问题说要删除重复的数字。然后，将数字保留在一个数组中，不要重复其他数字。例如， [0, 0, 1, 1, 2, 2, 1, 1 , 2, 2] 将是 [0, 1, 2 ] 这些数字应为时间复杂度 Big O(n) 和空间复杂度 O (1).

到目前为止，我所拥有的是下一个数字，检查下一个数字。它没有得到比它更远的数字。例如： [ 0, 1, 2 ,3 , 4, 5, 6, 2, 8, 9 ] 2 距离较远，但下面的代码不会检查。D[i+1]

我无法使用哈希图或哈希集。

    while (i < A.length) {

        i++;

        D = A;

        if (i < A.length - 1) {

            if (A[i] == D[i+1]){

                B[i] = D[i + 1];

            } else

                A[i] = A[i];

        }

    }

Answer 1

如果输入数组未排序（并且根据您的说法 - 未排序），您将无法在O(n)时间和空间上完成任务。O(1)这是不可能的，因为为了删除元素，您必须检查数组中之前或之后的任何位置是否有重复项。要检查重复项，您必须：扫描输入数组（这将导致O(n^2)整个算法的时间）使用额外的空间，例如使用Set（这将导致O(n)时间和O(n)空间）。所以基本上你必须权衡时间和空间，反之亦然。

Answer 2

这可能是不可能的，除非数组使用链表进行排序或将元素标记为 Integer.MIN_VALUE，应用此原则的“空间和时间权衡”如果我们需要更快的时间，那么我们需要权衡空间，反之亦然。如果使用数组，那么您可以将重复元素标记为 Integer.MIN_VALUE（在 java 中或在 c/c++ 中 -2^16），并且可以忽略该值。如果使用链表并且数组已排序，则只需检查下一个节点与前一个节点并删除下一个重复节点。

Answer 3

您必须“检查所有前面的内容”，而不是“检查下一个”。那么问题就变成了，“如何检查一个数字在恒定时间内是否存在于任意数量的其他元素中”？使用一个HashSet.&nbsp;基于哈希的结构的所有操作都是 O(1)。add()考虑使用和contains()的两种方法HashSet。我把写的代码留给你......