如何修改我的方法來搜索並刪除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）中的重複項？

回答

相關問題