My code passed, but I have used extra space. Is there any method to improve?


  • 0
    X
    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;
    	}
    
    }

  • 25
    M

    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;

  • 0
    F

    how clever you are!


  • 0
    C

    It can be improved:
    for(i=1....n) A[0]^=A[i];
    return A[0];


  • 0
    M

    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.


  • 1
    A
    for (;n > 1; n--) {
        A[n-2] = A[n-2]^A[n-1];
    }
    

    You don't even need the space for i, just be careful of the case that n == 1.


  • 0
    J
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    D

    Brilliant solution!
    I am wondering what if the inputs are floating points? Is there a similar trick, or should I use extra space?


  • 0
    M

    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.


  • 0
    C

    Very helpful, thanks! Be careful using float type as hash key since it is considered very unsafe.
    http://stackoverflow.com/questions/3399225/is-it-safe-to-use-floats-as-keys-of-hashtables


  • 0
    B

    I thought about this at the very beginning. However, you need to sort it first. And that takes n LOGn


  • 0
    B
    This post is deleted!

  • 0
    T

    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.