如何找到第一个非重复元素？

Question

如何在数组中找到第一个非重复元素.假设您只能为阵列的每个元素使用1位,并且时间复杂度应为O(n),其中n是数组的长度.请确保我以某种方式对内存要求施加约束.也有可能的是,每个字符串元素只需要一个额外的位就可以完成.如果有可能,请告诉我？

Answer 1

我想说没有基于比较的算法可以在 O(n) 内完成。因为您必须将数组的第一个元素与所有其他元素进行比较，第二个元素与除第一个元素之外的所有元素进行比较，第三个元素与除第一个元素之外的所有元素进行比较 = Sum i = O(n^2)。

（但这并不一定意味着没有更快的算法，请参阅排序：有证据表明，如果您基于比较，则排序速度不能快于 O(n log n) - 并且确实有一个更快的算法：桶排序，其中可以在 O(n) 内完成。

编辑：在其他评论之一中，我说了一些关于哈希函数的内容。我检查了一些有关它的事实，以下是哈希图方法的想法：

• 明显的方法是（伪代码）：

  for (i = 0; i < maxsize; i++)
      count[i] = 0;
  for (i = 0; i < maxsize; i++) {
     h = hash(A[i]);
     count[h]++;
  }
  first = -1;
  for (i = 0; i < maxsize; i++)
     if (count[i] == 0) {
        first = i;
        break;
     }
  }
  for (i = 0; hash(A[i]) != first; i++) ;
  printf("first unique: " + A[i]); 
  

• 有一些注意事项：

  1. 如何获得hash。我对完美哈希函数做了一些研究。事实上，您可以在 O(n) 内生成一个。（乔治·哈瓦斯（George Havas）等人的最小完美散列的最佳算法- 不确定这篇论文有多好，因为它声称时间限制 O(n) 但从非线性空间限制（这是计划错误，我希望我是）这并不是唯一看到的缺陷，但根据所有理论计算机科学，我知道时间是空间的上限（因为你没有时间在更多空间中书写）。但当他们说这是时我相信他们可能在 O(n) 内完成。

  2. 额外的空间 - 在这里我没有看到解决方案。上面的论文引用了一些研究，表明完美的哈希函数需要 2.7 位。使用附加count数组（您可以将其缩短为状态：空 + 1 个元素 + 超过 1 个元素），每个元素需要 2 个附加位（如果您假设可以以某种方式与上述 2.7 组合，则为 1.58），总计为额外的 5 位。