c++ - 如何在 C 或 C++ 的 O(n) 中删除数组中的重复元素？

Question

是否有任何方法可以在 O(n) 的 C/C++ 中删除数组中的重复元素？假设元素是 a[5]={1,2,2,3,4}那么结果数组应该包含 {1,2,3,4}该解决方案可以使用两个 for 循环来实现，但我相信那将是 O(n^2)。

Answer 1

当且仅当源数组已排序，这可以在线性时间内完成:

std::unique(a, a + 5); //Returns a pointer to the new logical end of a.

否则你必须先排序，这是(99.999% 的时间)n lg n。