如何在C或C ++中的O（n）中删除数组中的重复元素？
有没有什么方法可以在O（n）中的C / C ++中删除数组中的重复元素？ 假设元素是a[5]={1,2,2,3,4}那么结果数组应该包含{1,2,3,4}解决方案可以使用两个for循环来实现，但那将是O（n ^ 2）我相信。
如果且仅当源数组已排序时，可以在线性时间内完成：
std::unique(a, a + 5); //Returns a pointer to the new logical end of a.
否则你必须先排序，这是（99.999％的时间） n lg n 。
最好的情况是O(n log n) 。 对原始数组执行堆排序： O(n log n)及时， O(1) /就地空间。 然后按顺序运行数组，使用2个索引（source＆dest）来折叠重复。 这有副作用，不保留原始顺序，但由于“删除重复”没有指定要删除的重复项（第一个？第二个？最后一个？），我希望您不关心订单是否丢失。
如果您确实想要保留原始订单，则无法就地执行操作。 但是如果你在原始数组中创建指向元素的指针数组，在指针上完成所有工作，并使用它们在最后折叠原始数组，这是微不足道的。
任何声称它可以在O(n)时间和就地完成的人都是完全错误的，模拟了关于O(n)和就地意味着什么的一些论点。 一个明显的伪解决方案，如果你的元素是32位整数，就是使用一个初始化为全零的4千兆比特数组（大小为512兆字节），当你看到这个数字并翻过它时翻转一下这个位已经开启了。 当然，你正在利用n由常数限制的事实，所以从技术上讲，一切都是O(1)但具有可怕的常数因子。 但是，我确实提到过这种方法，因为如果n由一个小常数限定 – 例如，如果你有16位整数 – 这是一个非常实用的解决方案。
是。 由于哈希表上的访问（插入或查找）是O（1），因此可以删除O（N）中的重复项。
伪代码：
hashtable h = {} numdups = 0 for (i = 0; i < input.length; i++) { if (!h.contains(input[i])) { input[i-numdups] = input[i] h.add(input[i]) } else { numdups = numdups + 1 }
这是O（N）。
一些评论者指出哈希表是否为O（1）取决于许多事情。 但在现实世界中，通过良好的哈希，您可以期待恒定的性能。 并且可以设计一个O（1）的散列来满足理论家的要求。
我将建议北极光回答的变化，但我会在前面指出它是作弊。 基本上，它只能假设对数组中的值有一些严格的约束 – 例如，所有键都是32位整数。
而不是哈希表，想法是使用位向量。 这是O（1）内存要求，理论上应该让Rahul满意（但不会）。 对于32位整数，位向量将需要512MB（即2 ** 32位） – 假设8位字节，正如一些学者可能指出的那样。
正如Borealid应该指出的那样，这是一个哈希表 – 只需使用一个简单的哈希函数。 这确保不会发生任何碰撞。 可能发生碰撞的唯一方法是在输入数组中使用相同的值两次 – 但由于整点是忽略第二次和以后的出现，这无关紧要。
伪代码完整性……
src = dest = input.begin (); while (src != input.end ()) { if (!bitvector [*src]) { bitvector [*src] = true; *dest = *src; dest++; } src++; } // at this point, dest gives the new end of the array
只是真的很傻（但理论上是正确的），我还要指出，即使数组保持64位整数，空间要求仍然是O（1）。 恒定的术语有点大，我同意，你可能有64位CPU的问题实际上不能使用地址的完整64位，但……
举个例子。 如果数组元素是有界整数，则可以创建查找位数组。
如果找到3之类的整数，则打开第3位。 如果找到5之类的整数，则打开第5位。
如果数组包含元素而不是整数，或者元素没有限制，则使用哈希表是一个不错的选择，因为哈希表查找开销是一个常量。
unique()算法的规范实现看起来类似于以下内容：
template Fwd unique(Fwd first, Fwd last) { if( first == last ) return first; Fwd result = first; while( ++first != last ) { if( !(*result == *first) ) *(++result) = *first; } return ++result; }
该算法采用一系列有序元素。 如果未对范围进行排序，请在调用算法之前对其进行排序。 该算法将就地运行，并返回一个指向唯一序列的最后一个元素的迭代器。
如果你不能对这些元素进行排序，那么你就已经走投无路了，除了使用运行时性能比O（n）差的算法之外你别无选择。
该算法在O（n）运行时中运行。 在所有情况下，这是n的最大情况，而不是摊销时间。 它使用O（1）空间。
您给出的示例是一个排序数组。 只有在这种情况下才有可能（给定恒定的空间约束）