鉴于数字数组，除了一个号码的所有其他人，出现两次。给一个算法来查找只发生一次的数组中的数 [英] Given an array of numbers, except for one number all the others, occur twice. Give an algorithm to find that number which occurs only once in the array

问题描述

我能想到的是：

算法中：

1. 有一个哈希表，将储存的数量和其相关的计数
2. 解析阵列和增加计数的数量。
3. 现在，解析哈希表来获得，其计数为1的数目。

你们可以想到的解决方案比这更好的。 随着O（n）的运行时和不使用额外的空间

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

推荐答案

在红宝石的回答，假如学生单身，和所有其他完全两仪：

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一切！ HAHAHAH！

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

风铃草提醒我注射的方法，所以你可以在一行做到这一点：

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屋！