鉴于整数数组，找到的第一个整数，它是独一无二的 [英] Given an array of integers, find the first integer that is unique

问题描述

由于整数数组，找到的第一个整数，它是独一无二的。

Given an array of integers, find the first integer that is unique.

我的解决办法：使用的std ::地图

把整（编号为重点，其指数值）将其一一（为O（n ^ 2 LGN）），如果有重复，删除该条目从地图（O（LG N）），把所有的数字到地图后，迭代地图，找到最小的指数为O（n）的关键。

put integer (number as key, its index as value) to it one by one (O(n^2 lgn)), if have duplicate, remove the entry from the map (O(lg n)), after putting all numbers into the map, iterate the map and find the key with smallest index O(n).

为O（n ^ 2 LGN），因为地图需要做的排序。

O(n^2 lgn) because map needs to do sorting.

有效率不高。

其他更好的解决方案？

推荐答案

我认为，以下将是最佳的解决方案，至少基于时间/空间复杂度：

I believe that the following would be the optimal solution, at least based on time / space complexity:

步骤1： 存储整数的散列映射，其保持整数作为密钥，并将其显示为值的次数的计数。这通常是一个的为O（n）的操作和哈希表中的元素的插入/更新应该是恒定时间，平均。如果一个整数被发现出现两次以上，你真的不必递增使用另一计数（如果你不想）。

Step 1: Store the integers in a hash map, which holds the integer as a key and the count of the number of times it appears as the value. This is generally an O(n) operation and the insertion / updating of elements in the hash table should be constant time, on the average. If an integer is found to appear more than twice, you really don't have to increment the usage count further (if you don't want to).

步骤2： 进行第二次传过来的整数。在哈希表查找每一个和第一个有一个的出现次数就是你要找的人（即第一单出现整数）之一。这也是的 O（N）的，使得整个过程的 O（N）的。

Step 2: Perform a second pass over the integers. Look each up in the hash map and the first one with an appearance count of one is the one you were looking for (i.e., the first single appearing integer). This is also O(n), making the entire process O(n).

一些可能的优化，适用于特殊情况：

Some possible optimizations for special cases:

优化答：它可能会使用一个哈希表的一个简单的数组来代替。这保证O（1），即使在最坏的情况下，用于计算出现一个特定的整数的数目，以及其出现次数的查找。此外，此增强了实时性能，由于散列算法不需要被执行。有可能是一个打击，由于基准可能较差的地方（例如，一个更大的稀疏表与哈希表的实现有一个合理的负载系数）。然而，这将是整数序的非常特殊的情况，并且可以基于所述传入的整数（即，参考局部性差开始）。

Optimization A: It may be possible to use a simple array instead of a hash table. This guarantees O(1) even in the worst case for counting the number of occurrences of a particular integer as well as the lookup of its appearance count. Also, this enhances real time performance, since the hash algorithm does not need to be executed. There may be a hit due to potentially poorer locality of reference (i.e., a larger sparse table vs. the hash table implementation with a reasonable load factor). However, this would be for very special cases of integer orderings and may be mitigated by the hash table's hash function producing pseudorandom bucket placements based on the incoming integers (i.e., poor locality of reference to begin with).

在阵列中的每个字节将重新present计数（最多255个），再由该字节的指数psented $ P $的整数。这将仅是可能的，如果最低的整数和最高之间的差（即，有效整数域的基数）为足够小，使得该阵列将装入内存。特定整数的阵列中的索引。将其值减去最小整数present在数据集中。

Each byte in the array would represent the count (up to 255) for the integer represented by the index of that byte. This would only be possible if the difference between the lowest integer and the highest (i.e., the cardinality of the domain of valid integers) was small enough such that this array would fit into memory. The index in the array of a particular integer would be its value minus the smallest integer present in the data set.

例如在现代硬件上使用64位操作系统，这是完全可以想象，一个4GB的阵列可分配可以处理32位整数整个域。即使是较大的阵列是可以想象有足够的存储空间。

For example on modern hardware with a 64-bit OS, it is quite conceivable that a 4GB array can be allocated which can handle the entire domain of 32-bit integers. Even larger arrays are conceivable with sufficient memory.

的最小和最大的整数，就必须处理之前是已知的，或将需要通过数据使用最小最大算法来找出这个信息的另一种线性调整。

The smallest and largest integers would have to be known before processing, or another linear pass through the data using the minmax algorithm to find out this information would be required.

优化B：你可以优化的优化A 的进一步的，通过在每个整数最多2位（一个位表示presence和其他表示复数）。这将允许每字节四个整数重新presentation，延伸的阵列实现来处理整数更大的域可用存储器的给定量。更多位游戏可以在这里发挥到玉米preSS的重新presentation进一步，但它们只支持数据进来的特殊情况，因此不能被推荐用于静止大多一般情况。

Optimization B: You could optimize Optimization A further, by using at most 2 bits per integer (One bit indicates presence and the other indicates multiplicity). This would allow for the representation of four integers per byte, extending the array implementation to handle a larger domain of integers for a given amount of available memory. More bit games could be played here to compress the representation further, but they would only support special cases of data coming in and therefore cannot be recommended for the still mostly general case.

这篇关于鉴于整数数组，找到的第一个整数，它是独一无二的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！