使用数组并移动重复项结束

Question

我在接受采访时得到了这个问题,最后被告知有一种更有效的方法可以做到这一点,但仍然无法弄明白.您正在向函数传递一个整数数组和一个数组大小的整数.在数组中你有很多数字,有些例如重复1,7,4,8,2,6,8,3,7,9,10.你想获取该数组并返回一个数组,其中所有重复的数字都放在数组的末尾,以便上面的数组变成1,7,4,8,2,6,3,9,10,8,7.我使用的数字并不重要,我不能使用缓冲区数组.我打算使用BST,但必须保持数字的顺序(重复的数字除外).我无法弄清楚如何使用哈希表,所以我最终使用了一个双循环(n ^ 2可怕,我知道).如何使用c ++更有效地完成此操作.不寻找代码,只是想知道如何做得更好.

Answer 1

如下:

1. arr 是输入数组;
2. seen 是已遇到的数字哈希集;
3. l 是放置下一个唯一元素的索引;
4. r 是要考虑的下一个元素的索引.

由于您不是在寻找代码,因此这里有一个伪代码解决方案(恰好是有效的Python):

arr = [1,7,4,8,2,6,8,3,7,9,10]
seen = set()
l = 0
r = 0
while True:
  # advance `r` to the next not-yet-seen number
  while r < len(arr) and arr[r] in seen:
    r += 1
  if r == len(arr): break
  # add the number to the set
  seen.add(arr[r])
  # swap arr[l] with arr[r]
  arr[l], arr[r] = arr[r], arr[l]
  # advance `l`
  l += 1
print arr

在您的测试用例中,这会产生

[1, 7, 4, 8, 2, 6, 3, 9, 10, 8, 7]