import java.util.HashMap;
public class Solution {
public int singleNumber(int[] A) {
// initiate a map which is from index to number
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// the for loop cost O(n).
for (int i = 0; i < A.length; i++) {
int index = 0;
int number = 0;
number = A[i];
if (map.containsKey(number)) {
index = map.get(number);
++index;
} else {
++index;
}
map.put(number, index);
}
int solution = 0;
for (int j = 0; j < A.length; j++){
if(map.get(A[j]) == 1){
solution = A[j];
}
}
return solution;
}
}
My code passed, but I have used extra space. Is there any method to improve?


There is a way to use constant space, yes. While counting the objects and then looking for which occurs only once does work, you can do something similar with a set. In that solution, you add the object if it is not yet in the set, and remove it if it is. Then, the set is left with only the element that occurred once at the end.
Improving further on that process, since it is add/remove, a function that counters its effects if run a second time will allow you to find which element doesn't happen twice. The easiest one to use is exclusive or, ^. If you store the values in an int, and xor in each element as it occurs, at the end, only the singleton remains in the int.
Therefore, the constant space algorithm is as follows:
int num=0; for(int x : A) num ^= x; return num;

Except that changes the array passed into the function. Since arrays are passed by reference, any change to the array, such as storing the singleton in A[0] (the final result), will also occur in the array outside of the method. If that is not advertised, it could cause serious problems in future calculations. At the very least, if the singleton was not already the first element, you've changed the array so that the old first element is the new singleton and the old singleton has a twin in the first index.

In Java, there is no way I can think of that would allow for floating points to be used in this algorithm, so I'm pretty sure you need to go with the hashset's add/remove option, which still takes O(n) time, but requires O(n) space as well.
While the use of ^ would technically work for floats in this case, the Java compiler will not know what you are doing, and so will generate a compiler error if you try to use it on anything but long, short, int, or boolean.

Very helpful, thanks! Be careful using float type as hash key since it is considered very unsafe.
http://stackoverflow.com/questions/3399225/isitsafetousefloatsaskeysofhashtables

I guess @arthurhawk is right, you didn't need to sort it first.
after the for loop, the result will be in first element of the array.