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

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

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

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

需要注意的是,预期的算法不应该首先对数组进行排序.当一个元素被移除后,以下元素也必须向前移动.无论如何,元素尾部元素向前移动的元素值可以忽略不计.

更新:必须在原始数组中返回结果,并且不应使用辅助数据结构(例如哈希表).但是,我想订单保存不是必需的.

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

我女朋友建议的解决方案是合并排序的变体.唯一的修改是在合并步骤中,只是忽略重复的值.这个解决方案也是O(n log n).在这种方法中,排序/复制删除被组合在一起.但是,我不确定这是否会产生任何影响.

我之前已经发布了这个,但是我会在这里重现它,因为它非常酷.它使用散列,构建类似哈希集的东西.它保证在腋窝空间中是O(1)(递归是尾调用),并且通常是O(N)时间复杂度.算法如下:

取数组的第一个元素,这将是哨兵.

尽可能重新排序数组的其余部分,使每个元素位于与其散列对应的位置.完成此步骤后,将发现重复项.设置它们等于哨兵.

将索引等于哈希的所有元素移动到数组的开头.

将除了数组的第一个元素之外的所有等于sentinel的元素移动到数组的末尾.

正确散列的元素和重复元素之间的剩余部分将是由于冲突而无法放置在与其散列相对应的索引中的元素.递归处理这些元素.

这可以显示为O(N),在散列中没有提供病理场景:即使没有重复,在每次递归时也将消除大约2/3的元素.每个递归级别为O(n),其中小n是剩余元素的数量.唯一的问题是,在实践中,当重复很少时,即快速排序,即大量碰撞时,它比较慢.然而,当存在大量重复时,它的速度非常快.

编辑:在D的当前实现中,hash_t是32位.关于此算法的所有内容都假定在完整的32位空间中将存在非常少的哈希冲突(如果有的话).然而,碰撞可能在模数空间中频繁发生.然而,对于任何合理大小的数据集,这种假设很可能都是正确的.如果密钥小于或等于32位,则它可以是它自己的散列,这意味着完全32位空间中的冲突是不可能的.如果它更大,你根本无法将它们放入32位内存地址空间,因为它是一个问题.我假设在D的64位实现中hash_t将增加到64位,其中数据集可以更大.此外,如果这确实是一个问题,可以在每个递归级别更改散列函数.

这是D编程语言中的一个实现:

void uniqueInPlace(T)(ref T[] dataIn) {
    uniqueInPlaceImpl(dataIn, 0);
}

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
    if(dataIn.length - start < 2)
        return;

    invariant T sentinel = dataIn[start];
    T[] data = dataIn[start + 1..$];

    static hash_t getHash(T elem) {
        static if(is(T == uint) || is(T == int)) {
            return cast(hash_t) elem;
        } else static if(__traits(compiles, elem.toHash)) {
            return elem.toHash;
        } else {
            static auto ti = typeid(typeof(elem));
            return ti.getHash(&elem);
        }
    }

    for(size_t index = 0; index < data.length;) {
        if(data[index] == sentinel) {
            index++;
            continue;
        }

        auto hash = getHash(data[index]) % data.length;
        if(index == hash) {
            index++;
            continue;
        }

        if(data[index] == data[hash]) {
            data[index] = sentinel;
            index++;
            continue;
        }

        if(data[hash] == sentinel) {
            swap(data[hash], data[index]);
            index++;
            continue;
        }

        auto hashHash = getHash(data[hash]) % data.length;
        if(hashHash != hash) {
            swap(data[index], data[hash]);
            if(hash < index)
                index++;
        } else {
            index++;
        }
    }


    size_t swapPos = 0;
    foreach(i; 0..data.length) {
        if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
            swap(data[i], data[swapPos++]);
        }
    }

    size_t sentinelPos = data.length;
    for(size_t i = swapPos; i < sentinelPos;) {
        if(data[i] == sentinel) {
            swap(data[i], data[--sentinelPos]);
        } else {
            i++;
        }
    }

    dataIn = dataIn[0..sentinelPos + start + 1];
    uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}

一个更有效的实现

int i, j;

/* new length of modified array */
int NewLength = 1;

for(i=1; i< Length; i++){

   for(j=0; j< NewLength ; j++)
   {

      if(array[i] == array[j])
      break;
   }

   /* if none of the values in index[0..j] of array is not same as array[i],
      then copy the current value to corresponding new position in array */

  if (j==NewLength )
      array[NewLength++] = array[i];
}

在该实现中,不需要对阵列进行排序.此外,如果找到重复元素,则不需要在此之后将所有元素移位一个位置.

此代码的输出是array [],其大小为NewLength

这里我们从数组中的第二个elemt开始,并将它与数组中的所有元素进行比较,直到这个数组.我们持有一个额外的索引变量'NewLength'来修改输入数组.NewLength变量初始化为0.

数组[1]中的元素将与数组[0]进行比较.如果它们不同,那么数组[NewLength]中的值将被数组[1]修改并增加NewLength.如果它们相同,则不会修改NewLength.

所以,如果我们有一个数组[1 2 1 3 1],那么

在'j'循环的第一次传递中,数组[1](2)将与array0进行比较,然后2将被写入数组[NewLength] = array [1],因此数组将为[1 2],因为NewLength = 2

在'j'循环的第二次传递中,数组[2](1)将与array0和array1进行比较.这里因为数组[2](1)和array0是相同的循环将在这里打破.因为NewLength = 2,所以数组将是[1 2]

等等

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

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        push @newary, $i;
    }
}

#include 
#include 

size_t rmdup(int *arr, size_t len)
{
  size_t prev = 0;
  size_t curr = 1;
  size_t last = len - 1;
  while (curr <= last) {
    for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
    if (prev == curr) {
      ++curr;
    } else {
      arr[curr] = arr[last];
      --last;
    }
  }
  return curr;
}

void print_array(int *arr, size_t len)
{
  printf("{");
  size_t curr = 0;
  for (curr = 0; curr < len; ++curr) {
    if (curr > 0) printf(", ");
    printf("%d", arr[curr]);
  }
  printf("}");
}

int main()
{
  int arr[] = {4, 8, 4, 1, 1, 2, 9};
  printf("Before: ");
  size_t len = sizeof (arr) / sizeof (arr[0]);
  print_array(arr, len);
  len = rmdup(arr, len);
  printf("\nAfter: ");
  print_array(arr, len);
  printf("\n");
  return 0;
}