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);
}
}
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)