c++ - 给定一个整数数组，找到第一个唯一的整数

Question

给定一个整数数组，找到第一个唯一的整数。

我的解决方案:使用 std::map

将整数(数字作为键，其索引作为值)一一放入(O(n^2 lgn))，如果有重复，从 map 中删除条目 (O(lg n))，将所有数字放入映射后，迭代映射并找到索引最小的键 O(n)。

O(n^2 lgn) 因为 map 需要做排序。

效率不高。

其他更好的解决方案？

Answer 1

我相信以下将是最佳解决方案，至少基于时间/空间复杂度:

第 1 步: 将整数存储在 HashMap 中，该 HashMap 将整数作为键，将它出现的次数计数作为值。这通常是一个 O(n) 操作，平均而言，哈希表中元素的插入/更新应该是常数时间。如果发现某个整数出现两次以上，您真的不必进一步增加使用计数(如果您不想)。

第 2 步: 对整数执行第二次传递。在 HashMap 中查找每一个，第一个出现次数为 1 的就是您要查找的那个(即，第一个出现的整数)。这也是O(n)，使得整个过程O(n)。

针对特殊情况的一些可能的优化:

优化A:用一个简单的数组代替哈希表或许是可以的。即使在最坏的情况下，这也可以保证 O(1) 计算特定整数的出现次数以及查找其出现次数。此外，这增强了实时性能，因为不需要执行散列算法。由于引用的局部性可能较差(即，较大的稀疏表与具有合理负载因子的哈希表实现相比)，可能会受到影响。然而，这将适用于整数排序的非常特殊的情况，并且可以通过散列表的散列函数根据传入的整数生成伪随机桶放置来缓解(即，开始时引用的局部性差)。

数组中的每个字节代表该字节索引所代表的整数的计数(最多 255 个)。这只有在最低整数和最高整数之间的差异(即有效整数域的基数)足够小以至于该数组适合内存时才有可能。特定整数数组中的索引将是它的值减去数据集中存在的最小整数。

例如，在具有 64 位操作系统的现代硬件上，可以想象可以分配一个 4GB 的数组来处理整个 32 位整数域。如果有足够的内存，甚至可以想象更大的阵列。

在处理之前必须知道最小和最大整数，或者需要使用 minmax 算法对数据进行另一次线性传递以找出此信息。

优化 B:您可以进一步优化优化 A，每个整数最多使用 2 位(一位表示存在，另一位表示多重)。这将允许每个字节表示四个整数，扩展数组实现以处理给定可用内存量的更大整数域。可以在此处玩更多的位游戏以进一步压缩表示，但它们仅支持传入数据的特殊情况，因此不推荐用于仍然大多数一般情况。