c - 算法:从数组中删除重复整数的有效方法

Question

我在微软的面试中遇到了这个问题。

Given an array of random integers, write an algorithm in C that removes duplicated numbers and return the unique numbers in the original array.

例如输入:{4, 8, 4, 1, 1, 2, 9}输出:{4, 8, 1, 2, 9, ?, ?}

需要注意的是预期的算法不应该要求数组先排序。当一个元素被移除时，后面的元素也必须向前移动。无论如何，元素向前移动的数组尾部元素的值可以忽略不计。

更新:结果必须以原始数组的形式返回，不应使用辅助数据结构(例如哈希表)。但是，我想没有必要保留顺序。

更新 2:对于那些想知道为什么这些不切实际的限制的人，这是一个面试问题，所有这些限制都在思考过程中进行了讨论，以了解我如何提出不同的想法。

Answer 1

我女朋友建议的解决方案是归并排序的变体。唯一的修改是在合并步骤中，忽略重复值。这个解决方案也是 O(n log n)。在这种方法中，排序/去重组合在一起。不过，我不确定这是否有任何不同。