给定所有其他数字都出现两次的算法，该算法可找到一个仅在数组中出现一次的数字 [英] Algorithm to find a number which occurs only once in an array, given all the other numbers occur twice

问题描述

我能想到的是:

算法:

1. 具有一个哈希表，该表将存储数字及其关联的计数
2. 解析数组并增加数字的计数.
3. 现在解析哈希表以获取计数为1的数字.

你们能比这更好地考虑解决方案吗? 使用O(n)运行时且不占用额外空间

Can you guys think of solution better than this. With O(n) runtime and using no extra space

推荐答案

在Ruby中的答案，假设一个单例，而所有其他正好是两个样子:

An answer in Ruby, assuming one singleton, and all others exactly two appearances:

def singleton(array)
  number = 0
  array.each{|n| number = number ^ n}
  number
end

irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3

顺便说一下，

^是按位XOR运算符.对一切进行XOR！哈哈哈！

^ is the bitwise XOR operator, by the way. XOR everything! HAHAHAH!

Rampion使我想起了inject方法，因此您可以一行完成此操作:

Rampion has reminded me of the inject method, so you can do this in one line:

def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end

这篇关于给定所有其他数字都出现两次的算法，该算法可找到一个仅在数组中出现一次的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！