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)
1using System;
2
3class Solution {
4 public int SingleNonDuplicate(int[] nums) {
5 int left = 0, right = nums.Length - 1;
6 while (left < right) {
7 int mid = left + (right - left) / 2;
8 if (mid % 2 == 1) mid--;
9 if (nums[mid] == nums[mid + 1]) {
10 left = mid + 2;
11 } else {
12 right = mid;
13 }
14 }
15 return nums[left];
16 }
17
18 static void Main() {
19 Solution sol = new Solution();
20 int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
21 Console.WriteLine(sol.SingleNonDuplicate(nums));
22 }
23}This C# solution uses a binary search to find the unique element where all other elements are in pairs. By adjusting 'mid', the correct segment of the array can be quickly identified and searched.
The XOR operation cancels out all duplicates, leaving only the single unique element. This takes advantage of the property that x ^ x = 0 and x ^ 0 = x.