Simple JAVA solution w/o using extra memory


  • -4
    Y
    public class Solution {
    public int singleNumber(int[] A) {
        if (A.length<=3) return 1;
        
        Arrays.sort(A);
        
        //suppose that special number is at A[0]
        int extra=A[0];
        
        //if A[1] is different than A[0]
        //it means A[0] is the special number
        if (A[1] !=extra){
                return extra;
            }
        
        //if the A[1] is the same as A[0]
        // then the special number is in somewhere else
        for (int i=2;i<A.length; i++){
            
            if (A[i]==extra){
                continue;
            }
            
            //find a new number as potential special number
            extra=A[i];
            
            //if the number after the new number is different,
            //means that new number is the special number
            if (i+1==A.length || A[i+1] !=extra){
                return extra;
            }
             
        }
        return -1;
         
    }
    

    }


  • 8
    Y

    I think the code does not use extra memory, but the time is not linear, since sorting the array is not linear.


  • 0
    Z

    The sorting is at least O(nlogn), so it's not linear.


Log in to reply
 

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