在不使用哈希表的情况下从数组中删除重复项 [英] Remove duplicates from Array without using Hash Table

问题描述

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

i have an array which might contain duplicate elements(more than two duplicates of an element). I wonder if it's possible to find and remove the duplicates in the array:

• 不使用哈希表(严格要求)
• 不使用临时辅助阵列.对复杂性没有限制.

P.S:这不是家庭作业问题

在雅虎技术面试中被问到我的朋友

Was asked to my friend in yahoo technical interview

推荐答案

对源数组进行排序.查找连续个相等的元素.(即 std::unique 在 C++ 领域做了什么).总复杂度为 N lg N，如果输入已经排序，则仅为 N.

Sort the source array. Find consecutive elements that are equal. (I.e. what std::unique does in C++ land). Total complexity is N lg N, or merely N if the input is already sorted.

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

To remove duplicates, you can copy elements from later in the array over elements earlier in the array also in linear time. Simply keep a pointer to the new logical end of the container, and copy the next distinct element to that new logical end at each step. (Again, exactly like std::unique does (In fact, why not just download an implementation of std::unique and do exactly what it does? :P))

这篇关于在不使用哈希表的情况下从数组中删除重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！