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.
This approach exploits the properties of the XOR operation: a ^ a = 0 and a ^ 0 = a. We can XOR all elements, and since duplicates XOR to 0, only the unique element will remain.
Time Complexity: O(n)
Space Complexity: O(1)
1using System;
2
class Solution {
public int SingleNonDuplicate(int[] nums) {
int result = 0;
foreach (int num in nums) {
result ^= num;
}
return result;
}
static void Main() {
Solution sol = new Solution();
int[] nums = {3, 3, 7, 7, 10, 11, 11};
Console.WriteLine(sol.SingleNonDuplicate(nums));
}
}This C# code leverages the XOR operation in a similar manner, utilizing the inherent properties of XOR to cancel out duplicate entries and isolate the unique number.