使用数组，将重复元素移动到末尾

Question

我在面试中遇到了这个问题，最后被告知有一种更高效的方法来做这件事，但我仍然没有能够找到。你正在将一个整数数组和一个表示数组大小的整数传递到一个函数中。在数组中，你有很多数字，其中有一些是重复的，比如1,7,4,8,2,6,8,3,7,9,10。你想要将该数组转换成一个新的数组，使所有重复的数字都放在数组的末尾。所以上述数组将变成1,7,4,8,2,6,3,9,10,8,7。我使用的数字并不重要，而且我不能使用缓冲区数组。我打算使用BST，但必须保持数字的顺序（除了重复数字）。我无法想出如何使用哈希表，所以最终使用了双层循环（O(n^2)的时间复杂度，非常糟糕）。请问如何使用C++更高效地完成这个问题？我不需要代码，只需要一个更好的想法。

- Aaron

---

可能是重复的问题：如何从数组中删除重复项 - Hans Passant

请解释一下我应该使用什么公式来创建哈希表。如果是Java，我可以直接调用哈希表，但在C++中，我需要一些方法来组织它。我认为这可能是错误的。 - Aaron

@HansPassant 看起来不是重复的问题。他需要保持元素的相对顺序。 - Branko Dimitrijevic

@Aaron：请查看tune2fs和我的答案，了解如何使用任何稀疏容器（set/map/hash/...）。 - Mooing Duck

递归允许吗？（这使得“存储”未知数量的数据成为可能） - BatchyX

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]

- NPE

---

我大部分都懂。在C++中，set()是什么？ - Aaron

+1 表示“伪代码解决方案（恰好是有效的 Python 代码）”。 - Michał Bentkowski

Answer 2

我会这样做，创建一个原始数组两倍大小的数组并创建一组整数。

然后循环遍历原始数组，将每个元素添加到集合中，如果已存在，则将其添加到新数组的第二半部分，否则将其添加到新数组的第一半部分。

最终，您将获得一个类似于以下内容的数组：（使用您的示例）

1,7,4,8,2,6,3,9,10,-,-,8,7,-,-,-,-,-,-,-,-

然后，我会再次循环遍历原始数组，并使每个位置等于下一个非空位置（或0或其他您决定的值）。

这将使原始数组变成您的解决方案...

这最终是O(n)的，这是我能想到的效率。

Edit: since you can not use another array, when you find a value that is already in the
set you can move every value after it forward one and set the last value equal to the
number you just checked, this would in effect do the same thing but with a lot more operations.

- SomeoneRandom

---

你可以使用哈希表但不能使用数组？奇怪。 - SomeoneRandom

@Mooing Duck，在C++中，Set类在添加已经存在的元素时会返回true，因为集合不能有重复的元素。 - SomeoneRandom

我看错了，一个集合可以正常工作。请注意，您的数组中有空白，因此您必须使用指向int的指针。 - Mooing Duck

没错，我想填充空白处可以用他选择的任何内容，但既然他无法使用数组，那么他只能交换位置而不是使用另一个数组。 - SomeoneRandom

Answer 3

void remove_dup(int* data, int count) {
    int* L=data; //place to put next unique number
    int* R=data+count; //place to place next repeat number
    std::unordered_set<int> found(count); //keep track of what's been seen
    for(int* cur=data; cur<R; ++cur) { //until we reach repeats
        if(found.insert(*cur).second == false) { //if we've seen it
            std::swap(*cur,*--R); //put at the beginning of the repeats
        } else                    //or else
            std::swap(*cur,*L++); //put it next in the unique list
    }
    std::reverse(R, data+count); //reverse the repeats to be in origional order
}

http://ideone.com/3choA
虽然我不会提交这样没有注释的代码。另外请注意，unordered_set可能在内部使用自己的数组，比 data 更大。(此内容已根据aix的答案进行了重写，速度更快)

- Mooing Duck

Answer 4

#include <algorithm>

T * array = [your array];
size_t size = [array size];
                                           // Complexity:
sort( array, array + size );               // n * log(n) and could be threaded
                                           // (if merge sort)
T * last = unique( array, array + size );  // n, but the elements after the last
                                           // unique element are not defined

请查看sort和unique。

- Naszta

---

非常好，但不保留顺序。 - Chad

@Chad：如果没有sort，结果是未定义的。MSDN（和标准）说：在指定范围内删除相邻的重复元素。 - Naszta

我知道，我喜欢你的解决方案，但它不符合原帖要求保留顺序的要求。 - Chad

Answer 5

我有一段时间没有接触了，但我可能会从这个开始，看看它在处理更大的输入时如何扩展。我知道你没有要求代码，但在某些情况下，代码比解释更容易理解。

编辑：抱歉，我错过了不能使用缓冲数组的要求。

// returns new vector with dupes a the end
std::vector<int> move_dupes_to_end(std::vector<int> input)
{
    std::set<int> counter;
    std::vector<int> result;
    std::vector<int> repeats;

    for (std::vector<int>::iterator i = input.begin(); i < input.end(); i++)
    {
        if (counter.find(*i) == counter.end())
            result.push_back(*i);
        else
            repeats.push_back(*i);
        counter.insert(*i);
    }

    result.insert(result.end(), repeats.begin(), repeats.end());

    return result;
}

- dreamlax

Answer 6

我会使用一个额外的映射，其中键是数组中的整数值，值在开始时设置为0。现在我将遍历数组，并在键已经在映射中的情况下增加映射中的值。

最后，我将再次遍历数组。当映射中的整数值为1时，我不会改变任何内容。当映射中的整数值为2或更多时，我将用数组中的整数与最后一个整数交换。

这应该导致O(n*log(n))的运行时间。

- tune2fs

---

如果数组是[-2e9, 2e9]呢？ - Mooing Duck

Answer 7

如果您知道整数值的边界，B，和整数数组的大小，SZ，那么您可以执行以下操作：

1. 创建一个布尔值数组seen_before，其中有B个元素，初始化为0。
2. 创建一个结果数组result，其中有 SZ 个元素。
3. 创建两个整数变量，一个为 front_pos = 0，一个为 back_pos = SZ - 1。
4. 遍历原始列表：
   • 将整数变量val设置为当前元素的值
   • 如果seen_before[val]被设置为 1，则将数字放置在 result[back_pos]，然后将 back_pos 减 1。
   • 如果seen_before[val]没有被设置为 1，则将数字放置在 result[front_pos]，然后将 front_pos 加 1，并将seen_before[val]设置为 1。

一旦您完成对主列表的迭代，所有唯一的数字都将位于列表的前面，而重复的数字将位于列表的后面。有趣的部分是整个过程只需要一次遍历即可完成。请注意，这仅在您知道原始数组中出现的值的边界时才有效。

编辑：有人指出整数没有边界限制，因此，将seen_before初始化为具有 B 个元素的数组而不是一个map<int,bool>即可，然后继续如常。这应该会获得n * log(n) 的性能。

- Mr. Llama

---

他非常明确地表示整数没有（小于20亿）的界限。 - Mooing Duck

Answer 8

这可以通过迭代数组并标记第一个变化的索引来完成。稍后，将该标记索引值与下一个唯一值交换，然后递增该标记索引以进行下一次交换。

Java实现：

public static void solve() {
                Integer[] arr = new Integer[] { 1, 7, 4, 8, 2, 6, 8, 3, 7, 9, 10 };
        final HashSet<Integer> seen = new HashSet<Integer>();
        int l = -1;

        for (int i = 0; i < arr.length; i++) {
            if (seen.contains(arr[i])) {
                if (l == -1) {
                    l = i;
                }
                continue;
            }
            if (l > -1) {
                final int temp = arr[i];
                arr[i] = arr[l];
                arr[l] = temp;
                l++;
            }
            seen.add(arr[i]);
        }

    }

输出为 1 7 4 8 2 6 3 9 10 8 7。

- Pankaj Khattar

Answer 9

虽然不太美观，但它满足了将重复项移动到原地末尾的要求（无缓冲数组）

// warning, some light C++11
void dup2end(int* arr, size_t cnt)
{
   std::set<int> k;
   auto end = arr + cnt-1;
   auto max = arr + cnt;
   auto curr = arr;

   while(curr < max)
   {
      auto res = k.insert(*curr);

      // first time encountered
      if(res.second)
      {
         ++curr;
      }
      else
      {
         // duplicate:
         std::swap(*curr, *end);
         --end;
         --max;
      }
   }
}

- Chad

Answer 10

void move_duplicates_to_end(vector<int> &A) {
    if(A.empty()) return;
    int i = 0, tail = A.size()-1;
    while(i <= tail) {
        bool is_first = true;    // check of current number is first-shown
        for(int k=0; k<i; k++) { // always compare with numbers before A[i]
            if(A[k] == A[i]) {
                is_first = false;
                break;
            }
        }
        if(is_first == true) i++;
        else {
            int tmp = A[i]; // swap with tail
            A[i] = A[tail];
            A[tail] = tmp;
            tail--;
        }
    }

如果输入数组为{1,7,4,8,2,6,8,3,7,9,10}，那么输出为{1,7,4,8,2,6,10,3,9,7,8}。与你的答案{1,7,4,8,2,6,3,9,10,8,7}相比，前半部分相同，而后半部分不同，因为我将所有重复项与数组尾部交换。正如你所提到的，重复项的顺序可以是任意的。

- sunjerry