Sponsored
Sponsored
This approach leverages the sorted property of the array to perform a binary search, achieving a time complexity of O(log n). The key observation is that elements are paired, except for the single unique element. Thus, we can use the middle index to determine if the unique element is in the left or right half of the array based on the pairing pattern.
Time Complexity: O(log n)
Space Complexity: O(1)
1#include <stdio.h>
2
3int singleNonDuplicate(int* nums, int numsSize) {
4 int left = 0, right = numsSize - 1;
5 while (left < right) {
6 int mid = left + (right - left) / 2;
7 if (mid % 2 == 1) mid--; // Ensures mid is even
8 if (nums[mid] == nums[mid + 1]) {
9 left = mid + 2;
10 } else {
11 right = mid;
12 }
13 }
14 return nums[left];
15}
16
17int main() {
18 int nums[] = {1, 1, 2, 3, 3, 4, 4, 8, 8};
19 int size = sizeof(nums) / sizeof(nums[0]);
20 printf("%d\n", singleNonDuplicate(nums, size));
21 return 0;
22}The binary search here divides the array into two halves. If the middle element is equal to the element next to it and its index is even, it implies the single element is in the second half. Otherwise, it's in the first half. This process continues until left equals right, pointing to the single element.
The Python solution utilizes XOR to nullify paired elements, leaving the single unpaired element as the final result, a straightforward bit manipulation technique.