8 ms Java Solution without extra memory space and Explanation


  • 0
    G

    Number can be either 1st , or somewhere in middle or last number
    So If I sort the array and then check these 3 conditions we can find the number easily

    on Head and tail we just need to check number with next or previous entry
    In middle , we need to check both neighbors

    By default return -1;
    ...
    public class Solution {
    public int singleNumber(int[] nums) {
    if(nums.length==1) {

            return nums[0];
        }
        // First sort the arrays
        
        Arrays.sort(nums);
        //Now start looping
        for(int i=0;i<nums.length;i++) {
            // case 1 unique number is first
            if( i==0 && nums[i]!=nums[i+1] ) {
                return nums[i];
            }
            else if(i+2<nums.length-1 && (nums[i]!=nums[i+1])&&(nums[i+1]!=nums[i+2])) {
                return nums[i+1];
            }
            // case 2 unique number is somewhere in middle
            else if(i==nums.length-1) {
                if(nums[i]!=nums[i-1]) {
                    return nums[i];
                }
            }
            
            // case 3 unique number is last one
        }
        return -1;
    }
    

    }
    ...


  • 0
    J

    Sort the array take O(n log n) runtime complexity...


  • 0
    G

    Agreed,
    I mentioned about space time complexity because I did not use any extra memory


Log in to reply
 

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