我有一个数组，可能包含重复元素（一个元素可能有两个以上的重复）。 我想知道是否可能找到并删除数组中的重复项：
- 不使用哈希表（严格要求）
- 不使用临时辅助数组。 复杂度没有限制。
P.S: 这不是作业问题
这是在我的朋友yahoo技术面试时被问到的问题
8个回答
8
对源数组进行排序。找到连续相等的元素。（即在C++中std::unique所做的）。总复杂度为N lg N，如果输入已经排序，则仅为N。
要删除重复项，您可以在线性时间内将后面的元素复制到数组中较早的元素上。只需保持对容器的新逻辑结尾的指针，并在每个步骤中将下一个不同的元素复制到该新逻辑结尾即可（再次像std::unique一样）。 （事实上，为什么不下载 std::unique的实现并完全按照它所做的来做呢？:P）
- Billy ONeal
5
O(NlogN)：对数组进行排序并将连续相同的元素替换为一个副本。
O(N2)：运行嵌套循环以将每个元素与数组中剩余的元素进行比较，如果发现重复，则将重复项与数组末尾的元素交换并将数组大小减小1。
- codaddict
2
如何检查连续元素的相等性？ - SuperMan
1有几秒钟，我以为你在枚举步骤而不是替代方案...看了太多你的帖子，不相信会犯这样的错误，所以一直在琢磨 :-) - Tony Delroy
3
没有复杂性限制。
所以这很简单。
// 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--;
}
}
- Gabi Purcaru
2
你的代码很不错，但这是一个面试问题，面试官更喜欢O(NlogN)而不是O(N^2)。 - SuperMan
没有限制，但是如果有两个选项，最好选择其中一个更好的。我的朋友给出了O(N^2)的解决方案，等待面试结果。 - SuperMan
2
保留现有列表顺序的就地重复项删除，在二次时间内完成：
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)。
- Theo
1
在函数式编程语言中，您可以在一次遍历中将排序和唯一化（这是一个真正的词吗？）结合起来。让我们来看看标准快速排序算法：
如果您只想要唯一的条目，请将替换为
- 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: xs中所有小于或等于x的元素
用
left: xs中所有小于x的元素
这是一种一遍O(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]
- cfern
1
1这忽略了“不使用临时辅助数组”的要求。 - Tony Delroy
0
让我用Python来做这个。
array1 = [1,2,2,3,3,3,4,5,6,4,4,5,5,5,5,10,10,8,7,7,9,10]
array1.sort()
print(array1)
current = NONE
count = 0
# overwriting the numbers at the frontal part of the array
for item in array1:
if item != current:
array1[count] = item
count +=1
current=item
print(array1)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 5, 5, 5, 6, 7, 7, 8, 9, 10, 10, 10]
print(array1[:count])#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
最高效的方法是：
array1 = [1,2,2,3,3,3,4,5,6,4,4,5,5,5,5,10,10,8,7,7,9,10]
array1.sort()
print(array1)
print([*dict.fromkeys(array1)])#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#OR#
aa = list(dict.fromkeys(array1))
print( aa)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
- Soudipta Dutta
0
虽然它本身并没有使用哈希表，但我知道在幕后它是一个哈希表的实现。不过，我想发帖分享一下，以便能够帮助到大家。这段代码是用 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;
}
- d48
0
由于这是一道面试题，面试官通常会期望被问到问题的细节。
在不允许使用替代存储（即只允许 O(1) 存储，你可能会使用一些计数器/指针），显然需要进行破坏性操作，这可能值得向面试官指出。
现在真正的问题是：您是否想保留元素的相对顺序？也就是说，这个操作是否应该是稳定的？
稳定性极大地影响可用算法（因此也影响复杂度）。
最明显的选择是列出排序算法，毕竟，一旦数据排序完成，很容易获得唯一的元素。
但是，如果您想要稳定性，实际上不能对数据进行排序（因为您无法获得“正确”的顺序），因此我想知道如果涉及稳定性，是否可以在小于 O(N**2) 的时间内解决。
- Matthieu M.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
O(n^2)的答案，我个人不会雇用他们:P - Billy ONeal