Algorithm
Problem Name: 540. Single Element in a Sorted Array
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
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 105
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
int mid = (lo + hi) / 2;
while(lo < hi - 2){
if(nums[mid] == nums[mid + 1]) mid++;
if((hi - mid) % 2) lo = mid + 1;
else hi = mid;
mid = (lo + hi) / 2;
}
return nums[lo] == nums[lo + 1] ? nums[hi] : nums[lo];
}
};
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int singleNonDuplicate(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
return binarySearchHelper(nums, 0, nums.length - 1);
}
private int binarySearchHelper(int[] nums, int start, int end) {
if (start > end) {
return Integer.MIN_VALUE;
}
int mid = (start + end) / 2;
if (mid == 0 && mid + 1 < nums.length && nums[mid] != nums[mid + 1]) {
return nums[mid];
}
if (mid == nums.length - 1 && mid - 1 >= 0 && nums[mid] != nums[mid - 1]) {
return nums[mid];
}
if (mid + 1 < nums.length && nums[mid] != nums[mid + 1] && mid - 1 >= 0 && nums[mid] != nums[mid - 1]) {
return nums[mid];
}
return Math.max(binarySearchHelper(nums, start, mid - 1), binarySearchHelper(nums, mid + 1, end));
}
}
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const singleNonDuplicate = function(nums) {
let i = 0;
while (true) {
if (nums[i] == nums[i + 1]) {
i += 2;
} else {
return nums[i];
}
}
};
Copy The Code &
Try With Live Editor
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right = 0, len(nums)-1
while left<=right:
mid = (left+right)//2
if mid+1=0 and nums[mid] == nums[mid-1]:
if mid % 2 == 0: right = mid-2
else: left = mid+1
else: return nums[mid]
Copy The Code &
Try With Live Editor
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0540_SingleElementInASortedArray
{
public int SingleNonDuplicate(int[] nums)
{
int lo = 0, hi = nums.Length - 1;
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1])
lo = mid + 2;
else
hi = mid;
}
return nums[lo];
}
}
}
Copy The Code &
Try With Live Editor
Input
Output