给定一个整数数组，找到第一个唯一的整数。
我的解决方案：使用std::map
将整数（数字作为键，其索引作为值）一一放入其中(O(n^2 lgn))，如果有重复，则从地图中删除该条目(O(lg n))，将所有数字放入映射后，迭代映射并找到索引最小 O(n) 的键。
O(n^2 lgn)因为map需要做排序。
这效率不高。
其他更好的解决方案？
我相信以下将是最佳解决方案，至少基于时间/空间复杂度：
步骤1：
将整数存储在哈希映射中，该映射将整数作为键，并将其出现的次数作为值。这通常是一个O(n)平均而言，哈希表中元素的操作和插入/更新应该是恒定时间。如果发现一个整数出现两次以上，您实际上不必进一步增加使用计数（如果您不想）。
第2步：
对整数执行第二次传递。在哈希映射中查找每个，第一个出现次数为 1 的就是您要查找的那个（即第一个出现的整数）。这也是O(n)，使得整个过程O(n).
针对特殊情况的一些可能的优化：
优化A：可以使用简单的数组来代替哈希表。即使在最坏的情况下，这也保证了 O(1)，用于计算特定整数的出现次数以及查找其出现计数。此外，这还增强了实时性能，因为不需要执行哈希算法。由于引用局部性可能较差（即较大的稀疏表与具有合理负载因子的哈希表实现），可能会出现命中。然而，这适用于整数排序的非常特殊的情况，并且可以通过哈希表的哈希函数根据传入的整数生成伪随机存储桶放置来缓解（即，一开始引用的位置较差）。
数组中的每个字节都表示该字节索引所表示的整数的计数（最多 255）。只有当最低整数和最高整数之间的差异（即有效整数域的基数）足够小以使该数组适合内存时，这才是可能的。特定整数数组中的索引将是其值减去数据集中存在的最小整数。
例如，在具有 64 位操作系统的现代硬件上，可以想象可以分配一个 4GB 的数组来处理整个 32 位整数域。如果有足够的内存，甚至可以想象更大的阵列。
在处理之前必须知道最小和最大整数，或者需要使用最小最大算法对数据进行另一次线性遍历以找出该信息。
优化B：你可以优化优化A此外，每个整数最多使用 2 位（一位表示存在，另一位表示多重）。这将允许每个字节表示四个整数，从而扩展数组实现以在给定的可用内存量下处理更大的整数域。可以在这里玩更多的位游戏来进一步压缩表示，但它们仅支持传入数据的特殊情况，因此不能推荐用于仍然主要是一般的情况。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
