Single Element in a Sorted Array - LeetCode You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Your solution must run in O(log n) time and O(1) space.
Example 1: Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2 Example 2: Input: nums = [3,3,7,7,10,11,11] Output: 10
- code
class Solution {
public int singleNonDuplicate(int[] nums) {
int begin = 0, end = nums.length - 1;
while (begin < end){
int mid = begin + (end - begin) / 2;
if (mid % 2 != 0) mid-- ;
if (nums[mid] != nums[mid+1]) end = mid;
else {
begin = mid + 2;
}
}
return nums[end]; // or end
}
}
- code
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
lo = 0
hi = len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
lo = mid + 2
else:
hi = mid
return nums[lo]
- code
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
if len(nums) == 1: return nums[0]
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r-l) // 2
if nums[mid] == nums[mid-1]:
if (r - (mid+1) + 1) % 2 == 0:
r = mid - 2
else:
l = mid + 1
elif nums[mid] == nums[mid+1]:
if (r - (mid+2) + 1) % 2 == 0:
r = mid - 1
else:
l = mid + 2
else: return nums[mid]
return nums[l]
- code
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
if len(nums) == 1: return nums[0]
def isOnly(i):
if i == 0:
return nums[i] != nums[i+1]
elif i == len(nums) - 1:
return nums[i] != nums[i-1]
return nums[i] != nums[i-1] and nums[i] != nums[i+1]
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r-l) // 2
if isOnly(mid): return nums[mid]
elif nums[mid] == nums[mid-1]:
if (r - (mid+1) + 1) % 2 == 0:
r = mid - 2
else:
l = mid + 1
elif nums[mid] == nums[mid+1]:
if (r - (mid+2) + 1) % 2 == 0:
r = mid - 1
else:
l = mid + 2