从给定数字中查找唯一元素的最快方法
我有n个号码。 n <= 1000000。每个数字都是小于 10^9 的正整数。
可以肯定的是，只有一个数字会出现一次，其余的都会出现两次甚至多次。
我所知道的最短的解决方案是所有数字的异或结果。我想知道
- 标准 XOR 解决方案的复杂性是多少。
- 我们如何优化解决方案。
I have n numbers. n <= 1000000. Each number will be positive integer and less than 10^9.
It is sure that there will be only one number will occur once, rest will occur twice or even number of times.
The shortest solution I know is the result of XOR of all numbers. I want to know
- What will be the complexity of the standard XOR solution.
- How can we optimize the solution.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对所有数字进行异或运算的复杂度为 O(n)，因为您只需访问每个元素一次。
鉴于您的要求，我想不出任何进一步优化的方法。 XOR 是一种非常廉价的操作，问题的本质要求您至少访问每个元素一次：否则，您不可能知道哪个值是唯一的。
XORing all the numbers will be of O(n) complexity, since you'll need to visit each element only once.
I can't think of any way to optimize this further, given your requirements. XOR is a very cheap operation, and the nature of the problem requires you to visit each element at least once: otherwise, you cannot possibly know which value is unique.
XOR 算法是正确的算法，也是最快的算法。缓慢的部分是您读取输入的方式。
例如，C 中的
scanf比使用getchar手动处理您自己的数字算法慢（甚至更好的getchar_unlocked）。对于你提到的 SPOJ 问题，我通过进行此更改将时间从 1.35 秒提高到 0.14 秒。我确信剩下的 0.04 才能在网站上获得最佳时间，这只是由于比我的代码更好的低级 IO。The XOR algorithm is the right algorithm and the fastest one. The slow part is the way that you are reading the input.
For instance,
scanfin C is slower than handrolling your own number algorithm withgetchar(or even bettergetchar_unlocked). On the SPOJ problem that you mentioned, I got an improvement from 1.35s to 0.14s just by making this change. I'm sure that the remaining 0.04 to get the best time on the site is just due to better low-level IO than my code.您可以进行哈希处理。一个原始的解决方案是使用唯一的数字作为哈希表的键。如果可能的话，那么您可能可以使用哈希算法。一个简单的例子是使用数字作为数组中的索引。现在，空间会太多（我的意思是太多），但可以进一步优化。
You can go for hashing. A raw solution would be to use the unique number as a key to your hash table. If that is possible, then you can probably use the hashing algorithm. A simple example is to use the numbers as an index in an array. Now, the space will be too much (I mean too too much), but can be optimized further.