c – 给定一个整数数组,找到第一个唯一的整数

步骤1：
将整数存储在哈希映射中,该映射将整数保存为键,并将其显示为值的计数次数.这通常是O(n)操作,并且哈希表中元素的插入/更新平均应该是恒定时间.如果发现整数出现的次数超过两次,则实际上不必进一步增加使用次数(如果您不想这样做).

第2步：
对整数执行第二次传递.在哈希映射中查找每个,并且外观计数为1的第一个是您要查找的那个(即,第一个单个出现的整数).这也是O(n),使整个过程为O(n).

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

优化A：可以使用简单数组而不是哈希表.即使在最坏的情况下,这也可以保证O(1)计算特定整数的出现次数以及查看其出现次数.此外,这增强了实时性能,因为不需要执行散列算法.由于可能较差的引用局部性(即,较大的稀疏表与具有合理的加载因子的哈希表实现)可能存在命中.然而,这将是针对整数排序的非常特殊的情况,并且可以通过散列表的散列函数来减轻,该散列函数基于输入的整数产生伪随机桶放置(即,开始的参考的不良位置).

数组中的每个字节表示由该字节的索引表示的整数的计数(最多255).只有当最低整数和最高值(即有效整数域的基数)之间的差足够小以使该数组适合存储器时,这才是可能的.特定整数数组中的索引将是其值减去数据集中存在的最小整数.

例如,在具有64位OS的现代硬件上,可以想象可以分配4GB阵列,其可以处理32位整数的整个域.可以想象甚至更大的阵列具有足够的存储器.

在处理之前必须知道最小和最大的整数,或者使用minmax算法通过数据进行另一次线性传递以找出该信息.

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