算法：有效的方法来从一个数组中删除重复整数 [英] Algorithm: efficient way to remove duplicate integers from an array

问题描述

我从与微软的采访了这个问题。

  

由于随机整数数组，   在C中，去除写一个算法   重复号码和返回唯一的号码在原   数组。

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

一个需要注意的是，预期的算法不应该要求事先排好序的数组。并且当一个元件已被删除，以下元素必须向前移动为好。无论如何，在其中元素被向前移动所述阵列的尾部元件的值是可忽略的。

更新：的结果必须在原来的阵列和助手的数据结构（如哈希表）返回不应使用。不过，我想为了preservation是没有必要的。

UPDATE2：对于那些谁不知道为什么这些不切实际的限制，这是一个面试问题，所有这些限制都在思考的过程中讨论，看看我能拿出不同的想法。

解决方案

怎么样：

 无效rmdup（INT *数组，INT的长度）
{
    INT *目前，*结束=阵列+长度 -  1;

    对于（电流=阵列+ 1;阵列＆LT;结束;阵++，电流=阵列+ 1）
    {
        而（电流I =结束）
        {
            如果（*目前== *阵列）
            {
                *电流= * end--;
            }
            其他
            {
                当前++;
            }
        }
    }
}
 

应该是为O（n ^ 2）或更小。

I got this problem from an interview with Microsoft.

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

E.g Input: {4, 8, 4, 1, 1, 2, 9} Output: {4, 8, 1, 2, 9, ?, ?}

One caveat is that the expected algorithm should not required the array to be sorted first. And when an element has been removed, the following elements must be shifted forward as well. Anyway, value of elements at the tail of the array where elements were shifted forward are negligible.

Update: The result must be returned in the original array and helper data structure (e.g. hashtable) should not be used. However, I guess order preservation is not necessary.

Update2: For those who wonder why these impractical constraints, this was an interview question and all these constraints are discussed during the thinking process to see how I can come up with different ideas.

解决方案

How about:

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++;
            }
        }
    }
}

Should be O(n^2) or less.

这篇关于算法：有效的方法来从一个数组中删除重复整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！