给定一个整数数组，找到第一个唯一的整数
给定一个整数数组，找到第一个唯一的整数。
我的解决方案：使用std::map
将整数（数字作为键，其索引作为值）逐一放入(O(n^2 lgn)) ，如果有重复，则在将所有数字放入之后从地图中删除条目(O(lg n))映射，迭代映射并找到索引为O（n）最小的密钥。
O(n^2 lgn)因为地图需要进行排序。
效率不高。
更好的解决方案？
我相信以下将是最佳解决方案，至少基于时间/空间复杂性：
步骤1：将整数存储在哈希映射中，该映射将整数保存为键，并将其显示为值的次数计数。 这通常是O（n）操作，并且哈希表中元素的插入/更新平均应该是恒定时间。 如果发现整数出现的次数超过两次，则实际上不必进一步增加使用次数（如果您不想这样做）。
第2步：对整数执行第二次传递。 在哈希映射中查找每个，并且外观计数为1的第一个是您要查找的那个（即，第一个单个出现的整数）。 这也是O（n） ，使整个过程为O（n） 。
针对特殊情况的一些可能的优化：
优化A：可以使用简单数组而不是哈希表。 即使在最坏的情况下，这也可以保证O（1）计算特定整数的出现次数以及查看其出现次数。 此外，这增强了实时性能，因为不需要执行散列算法。 由于可能较差的引用局部性（即，较大的稀疏表与具有合理负载因子的哈希表实现）可能存在命中。 然而，这将是针对整数排序的非常特殊的情况，并且可以通过散列表的散列函数来缓解，该散列函数基于输入的整数产生伪随机桶放置（即，开始的参考的较差的局部性）。
数组中的每个字节表示由该字节的索引表示的整数的计数（最多255）。 只有当最低整数和最高整数（即有效整数域的基数）之间的差异足够小以使该数组适合存储器时，这才是可能的。 特定整数数组中的索引将是其值减去数据集中存在的最小整数。
例如，在具有64位OS的现代硬件上，可以想象可以分配4GBarrays，其可以处理32位整数的整个域。 可以想象甚至更大的arrays具有足够的存储器。
在处理之前必须知道最小和最大的整数，或者使用minmax算法通过数据进行另一次线性传递以找出该信息。
优化B：您可以进一步优化优化A ，每个整数最多使用2位（一位表示存在，另一位表示多重性）。 这将允许每个字节表示四个整数，扩展数组实现以处理给定量的可用内存的更大的整数域。 可以在这里播放更多位游戏以进一步压缩表示，但是它们仅支持特殊情况的数据进入，因此不能推荐用于仍然最常见的情况。
这一切都没有理由。 只使用2个for-loops和变量就可以得到一个简单的O(n^2)算法。
如果您在使用哈希映射时遇到了麻烦，那么它可能也就是@Micheal Goldshteyn所建议的
更新：我知道这个问题是1岁。 但正在查看我回答的问题，并发现了这一点。 认为有一个比使用哈希表更好的解决方案。
当我们说独特时，我们将有一个模式。 例如：[5,5,66,66,7,1,1,77]。 在这个让我们有移动窗口3.首先考虑（5,5,66）。 我们可以轻松地建立。 这里有重复。 因此，将窗口移动1个元素，这样我们得到（5,66,66）。 同样在这里。 转到下一个（66,66,7）。 再次重复这里。 接下来（66,7,1）。 这里没有重复！ 取中间元素，因为这必须是集合中的第一个唯一元素。 左元素属于dup，因此可以1.因此7是第一个唯一元素。
空间：O（1）时间：O（n）* O（m ^ 2）= O（n）*9≈O（n）
插入映射的是O(log n)而不是O(n log n)因此插入n键将是n log n 。 也更好地使用set 。
虽然它是O（n ^ 2），但是下面的系数很小，在缓存上也不算太差，并且使用快速的memmem() 。
for(int x=0;x
public static string firstUnique(int[] input) { int size = input.Length; bool[] dupIndex = new bool[size]; for (int i = 0; i < size; ++i) { if (dupIndex[i]) { continue; } else if (i == size - 1) { return input[i].ToString(); } for (int j = i + 1; j < size; ++j) { if (input[i]==input[j]) { dupIndex[j] = true; break; } else if (j == size - 1) { return input[i].ToString(); } } } return "No unique element"; }
@ user3612419
Solution given you is good with some what close to O(N*N2) but further optimization in same code is possible I just added two-3 lines that you missed. public static string firstUnique(int[] input) { int size = input.Length; bool[] dupIndex = new bool[size]; for (int i = 0; i < size; ++i) { if (dupIndex[i]) { continue; } else if (i == size - 1) { return input[i].ToString(); } for (int j = i + 1; j < size; ++j) { if(dupIndex[j]==true) { continue; } if (input[i]==input[j]) { dupIndex[j] = true; dupIndex[i] = true; break; } else if (j == size - 1) { return input[i].ToString(); } } } return "No unique element"; }