Problem Statement
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.
Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10
Note: Your solution should run in O(log n) time and O(1) space.
Solution
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int L=0, U=nums.size()-1;
int result;
while(L<=U)
{
if(L==U)
{
result = nums[L];
break;
}
int M = L+(U-L)/2;
int consideredLength = M-L+1;
if(consideredLength%2 == 1)
{
if(M-1>=0 && nums[M] == nums[M-1]) {
U = M-2;
}
else if(M+1<= nums.size()-1 && nums[M] == nums[M+1]) {
L = M+2;
}
else {
result = nums[M];
break;
}
}
else {
if(M+1<= nums.size()-1 && nums[M] == nums[M+1]) {
U = M-1;
}
else if(M-1>=0 && nums[M] == nums[M-1]) {
L = M+1;
}
else {
result = nums[M];
break;
}
}
}
return result;
}
};
Solution Thought Process
I solved this problem using binary search. First, we get the middle element of the range using low and high.
We get the length considered by calculating:
consideredLength = M-L+1
- Let's consider if this length is odd.
nums 1 1 2 2 3
idx 0 1 2 3 4
L = 0, U = 4
M = 0 + (4-0)/2 = 2
So[L, M] is odd in length. If this is the case, if nums[M] == nums[M+1], it means that the element can be found from element index M+2. So we make L=M+2
Let's see another case,
nums 1 2 2 3 3
idx 0 1 2 3 4
L = 0, U = 4
M = 0 + (4-0)/2 = 2
So [L, M] is odd in length. If nums[M] == nums[M-1] , it means that the element can be found before element index M-2 , included.
If those are not the case, then nums[M] is the result and we break the loop.
- Let's consider if the considered length is even.
nums 1 1 2 3 3 5 5
idx 0 1 2 3 4 5 6
L = 0, U = 6
M = 0 + (6-0)/2 = 3
So [L, M] is even in length. If nums[M] == nums[M+1], it means that the element can be found before element index M-1, included . So we make U = M-1
nums 1 1 2 2 3 5 5
idx 0 1 2 3 4 5 6
L = 0, U = 6
M = 0 + (6-0)/2 = 3
So [L, M] is even in length. If nums[M]==nums[M-1], it means that the element can be found from element index M+1. So we make L=M+1.
If we have got L and U as the same element, we return the element as the result.
Complexity
Time Complexity: O(logn), we are making the consideration space half in every iteration.
Space Complexity: O(1)
Top comments (0)