给定一个大小为n＆＃x2b; 1的整数，由元素[1，n]组成。所有元素都是唯一的，除了重复的k时

Question

我一直在尝试解决以下问题：

给您一个n+1整数的数组，其中所有元素都位于[1，n]中。您还可以认为，其中一个要素被复制了一定次，而其他元素则是不同的。开发一种算法以找到重复的数字及其重复的次数。

这是我的解决方案，我让k =重复数：

struct LatticePoint{ // to hold duplicate and k
   int a;
   int b;
   LatticePoint(int a_, int b_) : a(a_), b(b_) {}
   }
   
LatticePoint findDuplicateAndK(const std::vector<int>& A){

int n = A.size() - 1;
std::vector<int> Numbers (n);

for(int i = 0; i < n + 1; ++i){
   ++Numbers[A[i] - 1]; // A[i] in range [1,n] so no out-of-access
   }
   
int i = 0;
while(i < n){
   if(Numbers[i] > 1) {
      int duplicate = i + 1;
      int k = Numbers[i] - 1;
      LatticePoint result{duplicate, k};
      return LatticePoint;
}

因此，基本思想是：我们沿着数组进行，每次我们看到数字a [i]时，我们都会增加<的值代码>数字[A [i]] 。由于只有副本出现不止一次，因此值大于1的数字输入的索引必须是重复的数字，该数字具有条目的值重复数-1。o（n）o（n）<的算法/代码>在时间复杂性中，o（n）在太空中。

我想知道某人是否有时间和/或空间更好的解决方案？ （或者，如果我的解决方案中有任何错误...）

Answer 1

您可以将划痕空间缩小到n位，而不是n int s，只要您有或愿意编写bitset带有运行时指定的大小（请参阅boost :: Dynamic_bitset）。

您不需要收集重复计数，直到您知道哪个元素已重复，然后您只需要保持计数即可。因此，您需要跟踪的只是以前是否已经看到该值（因此，n位）。找到重复的值后，将计数设置为2，然后在矢量的其余部分运行，每次击中该值的实例时，请增加count。 （您初始化计数至2，因为到达那里时，您将完全看到其中两个。）

这仍然是O（n）空间，但是恒定因素要小得多。

Answer 2

代码的想法有效。

但是，由于n+1元素，我们可以实现其他时间和空间的权衡。

如果我们有一定数量的存储桶，我们将数字划分在之间，将n+1数字放置在意味着某些水桶必须比预期的要多。这是众所周知的 pigeOnhole原理。

因此，我们使用2个存储桶，一个用于范围1..floor（n/2），一个用于floor（n/2）+1..n..n。通过阵列，我们知道答案是哪一半。然后，我们将一半的一半分成一半，再过一遍，依此类推。这将导致二进制搜索，该搜索将以o（1）数据获得答案，而则带有CEIL（log_2（n））通过，每种时间都花费时间o o （n）。因此，我们在时间上得到答案o（n log（n））。

现在，我们不需要使用2桶。如果使用3，我们将使用ceil（log_3（n））通过。因此，随着我们增加了固定的存储桶数量，我们会占用更多空间并节省时间。还有其他权衡吗？

好吧，您展示了如何使用n存储桶中的1通过。您需要在2次通过中进行几个水桶？答案至少是sqrt（n） bucekts。以及三块根可能可以通过3次通过。等等。

因此，您将获得一个整个折衷家族的家庭，那里的水桶越多，所需的空间就越多，但是通行证就越少。而您的解决方案仅在极端，花费最多，时间最少。

Answer 3

这是一种Cheekier算法，它仅需要恒定空间，但可以重新安排输入向量。 （它只能重新定位；所有原始元素仍然存在。）

仍然是O（n）时间，尽管这可能不是完全明显的。
这个想法是尝试重新排列数组，以便[i]是我，直到找到重复。当我们尝试将元素放在正确的索引上时，副本将显示出来，事实证明该索引已经包含该元素。这样，我们找到了副本；我们有一个要移至[J]的价值，但是相同的值已经在[J]处。然后，我们浏览其余的数组，每次找到另一个实例时都会增加计数。

#include <utility>
#include <vector>
std::pair<int, int> count_dup(std::vector<int> A) {
  /* Try to put each element in its "home" position (that is,
   * where the value is the same as the index). Since the
   * values start at 1, A[0] isn't home to anyone, so we start
   * the loop at 1.
   */
  int n = A.size();
  for (int i = 1; i < n; ++i) {
    while (A[i] != i) {
      int j = A[i];
      if (A[j] == j) {
        /* j is the duplicate. Now we need to count them.
         * We have one at i. There's one at j, too, but we only
         * need to add it if we're not going to run into it in
         * the scan. And there might be one at position 0. After that,
         * we just scan through the rest of the array.
         */
        int count = 1;
        if (A[0] == j) ++count;
        if (j < i) ++count;
        for (++i; i < n; ++i) {
          if (A[i] == j) ++count;
        }
        return std::make_pair(j, count);
      }
      /* This swap can only happen once per element. */
      std::swap(A[i], A[j]);
    }
  }
  /* If we get here, every element from 1 to n is at home.
   * So the duplicate must be A[0], and the duplicate count
   * must be 2.
   */
  return std::make_pair(A[0], 2);
}

Answer 4

具有O（1）复杂性的平行溶液是可能的。

引入一系列原子布尔和两个原子整数，称为重复和计数。首先计数为1。然后在数字的索引位置并行访问数组，并在布尔值上执行测试和集合操作。如果已经设置了布尔值，请将数字分配给重复和增量计数。

该解决方案可能并不总是比建议的顺序替代方案更好。当然，如果所有数字都是重复的，那么不是。尽管如此，理论上它仍然具有恒定的复杂性。或重复数量的线性复杂性。我不太确定。但是，当使用许多内核时，它应该表现良好，尤其是在测试和增量操作不含锁定的情况下。