算法：从数组中删除重复整数的有效方法

Question

算法：从数组中删除重复整数的有效方法我在接受微软的采访时遇到了这个问题。给定一个随机整数数组，用C编写一个算法，删除重复的数字并返回原始数组中的唯一数字。例如输入：{4, 8, 4, 1, 1, 2, 9}产出：{4, 8, 1, 2, 9, ?, ?}一个警告是，预期的算法不应该要求首先对数组进行排序。当元素被移除时，以下元素也必须向前移动。无论如何，元素向前移动的数组尾部的元素值可以忽略不计。最新情况：必须在原始数组中返回结果，不应使用助手数据结构(例如哈希表)。不过，我想维持秩序是不必要的。UPDATE 2：对于那些想知道为什么会有这些不切实际的限制的人来说，这是一个面试问题，所有这些限制都是在思考过程中讨论的，看看我怎样才能想出不同的想法。

Answer 1

不如：

void rmdup(int *array, int length){
    int *current , *end = array + length - 1;

    for ( current = array + 1; array < end; array++, current = array + 1 )
    {
        while ( current <= end )
        {
            if ( *current == *array )
            {
                *current = *end--;
            }
            else
            {
                current++;
            }
        }
    }}

应该是O(n^2)或更少。

Answer 2

我女朋友提出的一个解决方案是合并排序的变化。唯一的修改是，在合并步骤中，只需忽略重复的值。这个解也是O(N Logn)。在这种方法中，排序/重复删除结合在一起。不过，我不确定这是否有什么区别。