DEV Community

Kardel Chen
Kardel Chen

Posted on

Leetcode 540 Single Element in a Sorted Array

class Solution {
    public int singleNonDuplicate(int[] nums) {
        return singleNonDuplicate(nums, 0, nums.length-1);
    }
    private int singleNonDuplicate(int[] nums, int l, int r){
        int mid = (r-l) / 2+l;
        int left = mid-l+1;
        // if there is only one element to search (nums[l])
        if(r == l){
            return nums[l];
        }
        // if nums[mid] is the unique element 
        if(nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]){
            return nums[mid];
        }else if(nums[mid] == nums[mid-1]){
            // if 
            if(left % 2 == 1){
                // if left is odd, then the unique element is at left [l, mid] 
                return singleNonDuplicate(nums, l, mid);
            }else{
                // if right is odd, then the unique is at [mid+1, r]
                return singleNonDuplicate(nums, mid+1, r);
            }
        }else{
            if(left % 2 == 1){
                // if left is odd, then the unique element is at right [mid, r]
                return singleNonDuplicate(nums, mid, r);
            }else{
                // if right is odd, then the unique element is at left [l, mid-1]
                return singleNonDuplicate(nums, l, mid-1);
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)