卸下阵列复制，而无需使用哈希表 [英] 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屋！