1

我创建了一个搜索重复项然后将重复项索引存储到另一个数组中的方法。然后我遍历我的大数组并移动所有条目而不重复。

现在，我的问题是它使用 O(N*N) 并且我正在使用额外的内存空间，因为我正在添加额外的数组。

怎么可能做到这一点？假设我需要了解如何在不使用其他库或 HashSet 的情况下完成此操作。

任何提示表示赞赏。

   public void dups()
   {
       int[] index = new int[100];

       int k = 0;
       int n = 0;
       int p = 0;

       for (int i = 0; i < elements; i++)
           for (int j = i + 1; j < elements; j++)
               if(a[j].equals(a[i]))
                   index[k++] = i;

       for (int m = 0; m < elements; m++)
           if (m != index[p])
               a[n++] = (T) a[m];
           else
               p++;

       elements -= k;
   }
4

4 回答 4

4

O(n)您（通常）找不到重复项。

不过在O(n*log n). 只需对数组进行排序（O(n*log n)），然后可以在O(n).

另一方面，如果您可以使用哈希表（如果您不想使用任何其他库，您可能不想这样做），您可以扫描数组并计算每个元素在数组中出现的频率. 之后，您可以遍历哈希表中的每个元素，并找到那些出现多次的元素。这将需要预期的运行时间O(n)，但不是确定性的O(n)。

最后，为什么我写你一般都找不到重复项O(n)？
可以想象几种特殊情况，在O(n). 例如，您的数组只能包含从 0 到 99 的数字。在这种情况下，您可以使用另一个数组（大小为 100）来计算每个元素在数组中出现的频率。这与哈希表的工作方式相同，但它的运行时间是确定性O(n)的。

O(n)当然，如果数组已经排序，则可以找到重复项的另一个示例。

于 2012-10-09T18:35:57.053 回答
1

使用 aHashSet在 O(n) 时间内执行此操作：

public <T> int removeDups(T[] original) {
    HashSet<T> unique = new HashSet<T>();
    for (T item: original) {
        unique.add(item);
    }

    int size = unique.size();
    int curr = 0;
    for (int i = 0; i < original.length; i += 1) {
        if (unique.remove(original[i])) {
            original[curr] = original[i];
            curr++;
        }
    }

    return size;
}

请注意，这取决于hashCode您的列表元素在桶中正确分配元素HashSet以实现 O(n) 的方法。在最坏的情况下，这是 O(n*m)，其中 m 是唯一元素的数量，所以你绝对应该测量它。

此实现修改数组，并返回唯一元素的数量。虽然数组可能比这个大，但超过那个点的元素应该被认为是垃圾。

它通过列表向其中添加项目HashSet（添加项目是O（1）），然后通过更新数组，所以它是O（n）（再次假设一个好的散列函数）。

于 2012-10-09T18:43:38.467 回答
0

HashMap 的默认实现是基于数组的并且是 O(n)。因此，如果您想要一个有趣的练习，您可以筛选 HashMap 的实现，以准确了解它如何散列其键。基本上，它使用键的 hashCode 并使用它来索引预定位置的数组（hashCode & arraylength - 1），并将值存储在该索引处。如果您要重复这个概念，同时使用值作为键和值，那么您的数组中将只有唯一的条目。

但是，如果您有大量重复项，但只有唯一值，您最终会得到一个包含很多空槽的数组。填充数组后，您只需循环一次即可删除任何空槽。（例如：将所有非空条目复制到列表中）

这将是 O(n)，但需要 2 次通过 - 一次填充数组，一次删除空槽。它还需要一个与现有数组长度相同的附加数组，以及一个较小的数组（或列表）用于最终的唯一值列表。

于 2012-10-09T19:10:16.237 回答
0

这不是 O(n) 因为哈希和等于比较，并使用 LinkedHashSet，它是 Java 标准库的一部分，但可能足够接近：

public void dups() {
    Set<Integer> uniques = new LinkedHashSet<>();
    for (int i = 0; i < elements.length; i++) {
        uniques.add(elements[i]);
    }
    // todo: copy the set into a list, then call toArray() to get an array.
}
于 2012-10-09T18:42:46.893 回答