卸下阵列复制,而无需使用哈希表 [英] 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:
- 在不使用哈希表(要求严格)
- 在不使用临时辅助阵列。复杂性没有限制。
PS :这不是在家工作的问题
有人问我的朋友在雅虎技术面试
Was asked to my friend in yahoo technical interview
推荐答案
排序源阵列。找到的连续的元素是相等的。 (即什么的std ::独特
确实在C ++中的土地)。总的复杂度是N LG 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 ::独特
没有(其实,为什么不下载的的实施的std ::独特
并做正是它: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屋!