如何修改我的方法来搜索并删除O（N）或O（N * log N）中的重复项？

我创建了一个搜索重复的方法，然后将重复索引存储到另一个数组中。然后我通过我的大阵列并移动所有条目而不重复。如何修改我的方法来搜索并删除O（N）或O（N * log N）中的重复项？

现在，我的问题是，这使用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; 
    }

来源

2012-10-09 HelpNeeder

不可能删除O（N）中的重复项。 –

http://stackoverflow.com/questions/4395668/remove-duplicates-from-array-without-using-hash-table –

他没有说哈希表不会被使用。 – FSP

你不能找到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-09 18:35:57 Misch

这是不是因为哈希的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-09 18:42:46 zoli

使用HashSet做到这一点在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; 
}

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

这个实现修改了这个数组，并返回唯一元素的数量。虽然数组可能比这更大，但过去那个元素应该被视为垃圾。

它在列表中添加项目以添加项目到HashSet（添加项目是O（1）），并且另一个更新数组，所以它是O（n）（同样，假设一个好的散列函数）。

来源

2012-10-09 18:43:38 Brigham

这不是O（n），而是O（n）*预期*（因为散列在常量*预期*时间内运行，而不是恒定时间）。 – leemes

我可能不应该通过创建另一个ArrayList来使我的程序使用额外的内存。 – HelpNeeder

@HelpNeeder - 听起来像[过早优化]（http://en.wikipedia.org/wiki/Program_optimization#When_to_optimize）给我。 – david

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

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

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

来源

2012-10-09 19:10:16

如何修改我的方法来搜索并删除O（N）或O（N * log N）中的重复项？

回答

相关问题