在不使用哈希表的情况下从Array中删除重复项

Question

我有一个数组,可能包含重复的元素(一个元素的两个以上重复).我想知道是否有可能找到并删除数组中的重复项:

• 不使用哈希表(严格要求)
• 不使用临时二级数组.对复杂性没有限制.

PS:这不是家庭工作问题

在雅虎的技术采访中被问到我的朋友

Answer 1

对源数组进行排序.找到相等的连续元素.(即std::uniqueC++中的内容).总复杂度为N lg N,如果输入已经排序,则仅为N.

要删除重复项,您可以在线性时间内从数组中较早的元素复制数组中较晚的元素.只需保留指向容器新逻辑端的指针,并在每一步将下一个不同元素复制到该新逻辑端.(再次,完全一样std::unique(事实上​​,为什么不下载一个实现std::unique并完全按照它做的那样做？:P))

Answer 2

O(NlogN):用一个副本对连续的相同元素进行排序和替换.

O(N ²):运行嵌套循环以将每个元素与数组中的其余元素进行比较,如果找到重复,则将副本与数组末尾的元素交换,并将数组大小减小1.