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)
1class Solution {
2 public int singleNonDuplicate(int[] nums) {
3 int left = 0, right = nums.length - 1;
4 while (left < right) {
5 int mid = left + (right - left) / 2;
6 if (mid % 2 == 1) mid--;
7 if (nums[mid] == nums[mid + 1]) {
8 left = mid + 2;
9 } else {
10 right = mid;
11 }
12 }
13 return nums[left];
14 }
15 public static void main(String[] args) {
16 Solution sol = new Solution();
17 int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
18 System.out.println(sol.singleNonDuplicate(nums));
19 }
20}This Java code uses a binary search to determine which half of the array the single element is located. The condition checks ensure that the search space is halved iteratively till the unique element is found.
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.