Is there any way to optimize this code. Code is Accepted but is it possible to improve it more.


  • 1
    D
    public int singleNumber(int[] input) {
            int length = input.length;
            
            if(length==1){
                return input[0];
            }
            
    		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for(int temp : input){
    			if(map.containsKey(temp)){
    				int value = map.get(temp) + 1;
    				map.put(temp, value);
    			} else {
    				map.put(temp,1);	
    			}
    		}
    		
    		int number = -1;
    
    		 Iterator it = map.entrySet().iterator();
    		    while (it.hasNext()) {
    		        Map.Entry<Integer,Integer> pairs = (Map.Entry)it.next();
    		        
    		        int val = (Integer) pairs.getValue();
    		        if(val == 1) {
    		        	number = pairs.getKey();
    		        }
    		    }
    		    return number;
            
        }

  • 21
    M

    Currently, your algorithm goes through the array and counts how many of each element there are. Depending on the hashing algorithm, this could be anywhere from O(n) to O(n^2) to complete. However, we can optimize this by using the knowledge that only 2-sets and a 1-set exist in the array, as set by the problem description.

    Since only singles and doubles occur, if something is a double of an element already in the set, we know both that it will not happen again in the array, and that it isn't the singleton. You can therefore either remove the element from the map or somehow cancel out that it was under consideration. By removing the doubled ints, by the end, only the element that occurs a single time will remain.

    Since the problem is dealing with ints, and there is only one number that is a 1-set, you can store the values of the ints in another int using xor, ^. All doubled ints will be added in the first time, and then have their effects cancel out when their twin is added in. After all the doubles cancel, only the 1-set int remains in the store.

    int num=0;
    for(int i : A) num^=i;
    return num;

  • 0
    R

    wanderfull solution! But I think num is using some extra space,how about this :

    
    class Solution:
        # @param A, a list of integer
        # @return an integer
        def singleNumber(self, A):
            num = A[0]
            for i in xrange(1,len(A)):
                num ^= A[i]
            return num
    
    

  • 0
    M

    Depending on how you are thinking of your algorithm, there are two possible problems I see. If you see num as a pointer to A[0], so that num doesn't use extra space, then the function will end up changing A and being different on alternating runthroughs unless A[0] was the singleton.

    If you interpret it the other way, where num is copying the value of A[0], then it seems like it's exactly the same algorithm as mine, just in python and having the first iteration of the loop be in the declaration, so it would be using the extra space as well.


  • 0
    R

    thanks for your comment, I used to think num is a pointer to A[0] in Python. Seems I have made a mistake...


  • 0
    M

    I'm pretty sure num isn't considered a pointer, but I'm not positive, which is why I gave both problems. You actually need that extra space or you have a high chance of changing the array you are given, which causes the next run-through to give a different answer.


Log in to reply
 

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