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

问题描述

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

I got this problem from an interview with Microsoft.

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

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, ?, ?}代码>

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.

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

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.

推荐答案

怎么样:

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) 或更小.

Should be O(n^2) or less.

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