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

一尘不染

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

algorithm

我在接受Microsoft采访时遇到了这个问题。

给定一个随机整数数组，用C编写一个算法，该算法将删除重复的数字并返回原始数组中的唯一数字。

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

一个警告是预期的算法不应要求首先对数组进行排序。并且，当一个元素被删除后，以下元素也必须向前移动。无论如何，在元素向后移动的数组尾部的元素值可以忽略不计。

更新： 结果必须在原始数组中返回，并且不应使用辅助数据结构（例如，哈希表）。但是，我认为没有必要保留订单。

Update2：
对于那些想知道为什么这些不切实际的约束条件的人，这是一个面试问题，并且在思考过程中讨论了所有这些约束条件，以了解我如何提出不同的想法。

阅读 212

2020-07-28

共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）或更小。

2020-07-28