Two ways to solve this


  • 1
    L

    I admit that I didn't initially read the question to do it in O(logn). That is a simple solution with O(n) with a XOR.

    
    public int singleNonDuplicateUsingXOR(int[] nums) {
            if(nums==null || nums.length==0) {
                return -1;
            }
            
            int first = nums[0];
            for(int i =1;i<nums.length;i++) {
                first ^= nums[i];
            }
            return first;
        }
    

    Now, since the first is not allowed, the only option is a binary search since the array is already sorted. The idea should be to read to an index and see if the left or right are part of the pairs and then select the part of the array that is odd after taking pairs into consideration. Here is the code.

      public int singleNonDuplicate(int[] arr) {
            if(arr==null || arr.length==0) {
                return -1;
            }
            
            int i=0,j=arr.length-1;
            while(i<=j) {
                //pivot.
                int pivot = (j-i)/2 + i;
                if(i==j) {
                    return arr[pivot];
                }
                if(arr[pivot]==arr[pivot-1]) {
                    //left side.
                    //find the odd side.
                    if((pivot-1)%2!=0) {
                        j = pivot-1;
                    }
                    else {
                        i = pivot+1;
                    }
                }
                else if(arr[pivot]==arr[pivot+1]) {
                    if((arr.length-1-(pivot+1))%2!=0) {
                        i = pivot+1;
                    }
                    else {
                        j = pivot-1;
                    }
                }
                else
                {
                    //last element?
                    if(pivot+1==arr.length-1) {
                        return arr[pivot+1];
                    }
                    else {
                        return arr[pivot];
                    }
                }
                
            }
            
            return arr[i];
        }
    

Log in to reply
 

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