小编典典

给定所有其他数字都出现两次的算法,该算法可找到一个仅在数组中出现一次的数字

algorithm

我能想到的是:

算法:

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

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


阅读 239

收藏
2020-07-28

共1个答案

小编典典

Ruby中的一个答案,假设一个单例,而其他所有则正好有两个表象:

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一切!哈哈哈哈!

Rampion让我想起了inject方法,因此您可以在一行中完成此操作:

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