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
The given task is to find the single element in a sorted array where every other element appears exactly twice. The provided code solves this problem using a linear approach, which iterates through the array to identify the unique element. The solution starts by calculating the size of the array (`n`) and checking for a special case: if the array contains only one element, it directly returns that element, as it is the answer. Otherwise, the code uses a `for` loop with a step size of 2 to check pairs of adjacent elements. Since all elements except one appear exactly twice in sorted order, comparing `nums[i]` with `nums[i+1]` will reveal the unique element when the condition `nums[i] != nums[i+1]` is satisfied. The unique element is then returned.
For example, if the input is `nums = [1,1,2,3,3,4,4,8,8]`, the function iterates through the array, skipping pairs until it reaches the index where the single element (`2`) exists, and returns it. Similarly, for `nums = [3,3,7,7,10,11,11]`, the function identifies `10` as the unique element by comparing adjacent elements.
While this solution is simple and works efficiently for small arrays, its time complexity is **O(n)** because it involves iterating through the array linearly. However, the problem explicitly requires a solution with a time complexity of **O(log n)**, which suggests the use of a binary search. A binary search would leverage the sorted nature of the array and the property of paired elements to halve the search space in each step, enabling a logarithmic runtime. Nonetheless, the current approach is functional and correctly identifies the single element in the array.
CODE:
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n=nums.size();
int i,h;
if(n==1){
return nums[0];
}
for(i=0;i<n;i+=2){
if(nums[i]!=nums[i+1]){
h=nums[i];
return h;
}
}
return -1;
}
};
0 Comments