從數組中刪除重複項而不使用哈希表

Question

我有一個數組可能包含重複元素（超過兩個元素的重複項）。不知是否有可能找到並刪除數組中的重複：

• 不使用哈希表（嚴格要求）
• 不使用臨時輔助陣列。複雜性沒有限制。

P.S：這不是家庭作業問題

有人問我的朋友在雅虎技術面試

Answer 1

排序源陣列。連續查找相等的元素。 （即在C++中有什麼std::unique土地）。總的複雜度是N lg N，或者如果輸入已經排序，則僅爲N.

要刪除重複項，您可以在線性時間內將數組中稍後的元素複製到數組中較早的元素上。只需將指針指向容器的新邏輯末尾，並在每個步驟中將下一個不同的元素複製到該新的邏輯末尾。 （再次，完全像std::unique那樣（實際上，爲什麼不直接下載 an implementation of std::unique並且做它到底做了什麼？：P））

Answer 2

O（NlogN）：排序並用一個副本替換連續的相同元素。如果發現重複，則使用嵌套循環比較每個元素與數組中的其餘元素，如果發現重複，則將該副本與數組末尾的元素進行交換，並將數組大小減1 。

Answer 3

就地重複的去除，保留列表的現有秩序，在二次時間：

for (var i = 0; i < list.length; i++) { 
    for (var j = i + 1; j < list.length;) { 
    if (list[i] == list[j]) { 
     list.splice(j, 1); 
    } else { 
     j++; 
    } 
    } 
} 

關鍵是要開始i + 1內循環，而不是遞增內部計數器，當你刪除元件。

代碼是JavaScript，splice(x, 1)刪除了元素x。

如果爲了保存是不是一個問題，那麼你就可以做到這一點更快：

list.sort(); 

for (var i = 1; i < list.length;) { 
    if (list[i] == list[i - 1]) { 
    list.splice(i, 1); 
    } else { 
    i++; 
    } 
} 

這是線性的，除非你的排序，你應該，所以它的排序的順序 - - 在大多數情況下n×log（n）。

Answer 4

對複雜性沒有限制。

所以這是小菜一碟。

// A[1], A[2], A[3], ... A[i], ... A[n] 

// O(n^2) 
for(i=2; i<=n; i++) 
{ 
    duplicate = false; 
    for(j=1; j<i; j++) 
     if(A[i] == A[j]) 
      {duplicate = true; break;} 
    if(duplicate) 
    { 
     // "remove" A[i] by moving all elements from its left over it 
     for(j=i; j<n; j++) 
      A[j] = A[j+1]; 
     n--; 
    } 
} 

Answer 5

在函數式語言中，你可以在一個遍中結合排序和單一化（是一個真正的單詞？）。 讓我們以標準的快速排序算法：如果你只想唯一條目

- Take the first element of the input (x) and the remaining elements (xs) 
- Make two new lists 
- left: all elements in xs smaller than or equal to x 
- right: all elements in xs larger than x 
- apply quick sort on the left and right lists 
- return the concatenation of the left list, x, and the right list 
- P.S. quick sort on an empty list is an empty list (don't forget base case!) 

，更換

left: all elements in xs smaller than or equal to x

與

​​

這是一個通Ø （n log n）算法。

例實施F＃：

let rec qsort = function 
    | [] -> [] 
    | x::xs -> let left,right = List.partition (fun el -> el <= x) xs 
       qsort left @ [x] @ qsort right 

let rec qsortu = function 
    | [] -> [] 
    | x::xs -> let left = List.filter (fun el -> el < x) xs 
       let right = List.filter (fun el -> el > x) xs 
       qsortu left @ [x] @ qsortu right 

而在交互模式測試：

> qsortu [42;42;42;42;42];; 
val it : int list = [42] 
> qsortu [5;4;4;3;3;3;2;2;2;2;1];; 
val it : int list = [1; 2; 3; 4; 5] 
> qsortu [3;1;4;1;5;9;2;6;5;3;5;8;9];; 
val it : int list = [1; 2; 3; 4; 5; 6; 8; 9] 

Answer 6

因爲它是一個面試問題通常是由面試官預計將被問及的問題精度。在沒有其他存儲允許的情況下（即允許使用O（1）存儲，因此你可能會使用一些計數器/指針），看起來很明顯，預計會有破壞性的操作，所以值得指出的是面試官。

現在真正的問題是：你想保留元素的相對順序嗎？即這個操作應該是穩定的嗎？

穩定性對可用算法（以及複雜度）的影響很大。

最明顯的選擇是列出Sorting Algorithms，畢竟，一旦數據被排序，就很容易獲得獨特的元素。

但是如果你想要穩定性，你實際上不能對數據進行排序（因爲你無法獲得「正確」的順序），因此我懷疑它是否可以在小於O（N ** 2） 。

Answer 7

本身不使用散列表，但我知道幕後是一個實現。儘管如此，我想我可能會發布，以防它可以幫助。這是在JavaScript和使用一個關聯數組來記錄重複越過

function removeDuplicates(arr) { 
    var results = [], dups = []; 

    for (var i = 0; i < arr.length; i++) { 

     // check if not a duplicate 
     if (dups[arr[i]] === undefined) { 

      // save for next check to indicate duplicate 
      dups[arr[i]] = 1; 

      // is unique. append to output array 
      results.push(arr[i]); 
     } 
    } 

    return results; 
}