Leetcode 540 Single Element in a Sorted Array
Kardel Chen
Posted on January 16, 2022
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);
}
}
}
}
💖 💪 🙅 🚩
Kardel Chen
Posted on January 16, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
githubcopilot AI Innovations at Microsoft Ignite 2024 What You Need to Know (Part 2)
November 29, 2024