从数组中删除重复项而不使用哈希表

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; 
}