从Array中删除重复项，而不使用哈希表 [英] Remove duplicates from Array without using Hash Table

问题描述

我有一个数组，它可能包含重复的元素（多于两个元素的重复）。我想知道是否可以找到并删除数组中的重复项：

• 不使用哈希表（严格要求）


• 不使用临时辅助数组。

PS ：这不是家庭工作问题

在雅虎技术面试中要求我的朋友

解决方案

源数组。查找相等的连续元素。 （即，C ++中的 std :: unique ）。总复杂度为N lg N，如果输入已经被排序，则仅为N。

要删除重复项，可以从数组中的后面的元素复制元素阵列也在线性时间。只需保留指向容器新逻辑端的指针，并在下一个步骤将下一个不同元素复制到该新的逻辑末尾。 （再次，完全像 std :: unique （实际上，为什么不只是下载 std :: unique 的实现，并且做的完全是什么？：P））

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:

• without using Hash Table (strict requirement)
• without using a temporary secondary array. No restrictions on complexity.

P.S: This is not Home work question

Was asked to my friend in yahoo technical interview

解决方案

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.

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))

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