社区 › 研发应用 › [google面试题]Write 
an
algorithm
 (in 
a 
language
 of
 your
 choice)
that 
finds 
the
 integer 
that 
appears 
only 
once.

邢城 发表于 2013-7-30 17:20:49

[google面试题]Write 
an
algorithm
 (in 
a 
language
 of
 your
 choice)
that 
finds 
the
 integer 
that 
appears 
only 
once.

孙宏雷 发表于 2013-7-30 17:40:40

Good Answer:Set up a hashset that we will put the integers from the array into.Have a second variable that will keep a sum.Start going through the array and foreach integer,check to see if it's already in the hashset.If it is not,add that integer to the sum and store that integer in the hashset.If it is in the hashset,subtract that integer from the sum.When the algorithm finishes going through the array,the sum variable should be equal to the integer we were looking for,since it is the only number we never subtracted from the sum.This takes O(n) time and O(n)s pace.int oddManOut(int[] array) { HashSet<Integer> s = newHashSet<Integer>(); intsum = 0; for(int i = 0; i < array.length; i++) { if(s.contains(array)) { sum= sum - array; }else { s.add(array); sum= sum + array; } } return sum;}Really Awesome Answer:XOR all the values of the array together!Since XOR iscommutative and is its own inverse,each integer in the array that appears twice will cancel it selfout,and we'll be left with the integer we're looking for. This takes O(n) time and O(1) space.We told you bitwise stuff washandy!int oddManOut(int[] array) { intval = 0; for(int i = 0; i < array.length; i++) { val^= array; } return val;}

查看完整版本: [google面试题]Write 
an
algorithm
 (in 
a 
language
 of
 your
 choice)
that 
finds 
the
 integer 
that 
appears 
only 
once.