2

我有一个数组，我需要摆脱它的数组，没有重复。我必须将那些具有最小顺序的独特元素留在原始数组中。这大概是我的意思

NoDuplicate(A, value)
  for int i = 0 to i < A.length
    if A[i] == value
      return true
    i++
  return false

StableRemoveAlgo(A)      
  for int i = 0 to i < A.length
    if NoDuplicate(result, A[i])
      result.append(A[i])
  return result

如果有比这个简单的算法更快的算法？

更新：我无法对数组进行排序。我需要一个“稳定”版本的重复删除算法。所以，如果A[i] == A[j] and i < j算法必须删除元素A[j]

4

4 回答 4

7

在遍历数组时，将遇到的每个（唯一）元素放入哈希表或树中。这将使您能够在检查第一个元素时快速检查k您是否在前面的k-1元素中遇到了相同的数字。

一棵树会给你整体O(n log(n))时间复杂度。具有良好哈希函数的哈希表会做得更好（可能O(n)）。

于 2011-05-06T15:41:33.347 回答
2

如果您不需要 O(1) 空间，只需为原始数组的元素（最初为 0,1,2,...,n-1）创建一个索引数组，并使用索引号对它们进行排序解决在其他方面比较相等的元素之间的比较。这是在不稳定排序之上构建稳定排序的标准方法。之后，您只需遍历索引数组即可找到要从原始数组中删除的元素。

于 2011-05-09T21:13:59.667 回答
2

如果元素的域是有限的（并且不是太大），您可以进行二进制计数排序。那将是O（n）。

否则，您可以在遍历数组时使用临时哈希表来存储元素，并且仅当哈希表中当前不存在该项目时才将元素放入输出数组中。在典型情况下，这将是 O(n)。

于 2011-05-06T15:45:46.370 回答
0

您是否允许就地执行操作并对数组进行排序？如果你这样做很简单：

sort(array) // use a stable sorting algorithm of your choice.
i = 0 //how many unique elements we have already spotted
j = 0 //how many array elements we have checked

while(j < arr.length){
    //found a new value:
    array[i] = array[j];

    //find next value in array that is different
    while(j < arr.length && array[i] == array[j]){
        j++;
    }
}
arr.length = i;

如果你需要自己实现一个稳定的排序算法，最简单的可能是 Mergesort。

但是，在这种情况下，您可以改为直接调整合并例程以忽略相似的值（优先于较早的值），而不是返回所有值。

于 2011-05-06T17:11:28.033 回答