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

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;}