1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int singleNonDuplicate(int[] nums) {
if (nums.length == 1)
return nums[0];
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int leftCount = mid - left + 1;
if (leftCount % 2 == 0) {
if (nums[mid] == nums[mid - 1]) {
left = mid + 1;
} else if (nums[mid] == nums[mid + 1]) {
right = mid - 1;
} else {
return nums[mid];
}
} else {
if (nums[mid] == nums[mid + 1]) {
left = mid + 2;
} else if (nums[mid] == nums[mid - 1]) {
right = mid - 2;
} else {
return nums[mid];
}
}
}
return nums[left];
}
}
|
binary search很好想到. 但是如何确定mid - 1和mid + 1不会越界. 我们的逻辑是把target value锁定在left和right之间(包含left和right), 同时不会保留出现两次的数字中的一个. 要么都保留, 要么都不保留. 而出界的情况只有一种就是区间长度为2, 此时mid - 1出界. 但如果是这种情况, 这是不符合我们的假设的. 因为我们的区间中有一个是target value, 那剩下那一个呢? 它则是可以构成pair中的一个, 我们对于这种value的要求是要么一个都不包括, 要么都包括. 于是这种假设不成立. 因此, 唯一可能出现越界的可能被我们排出, mid - 1和mid + 1都是不会越界的.
时间复杂度: O(logn)
空间复杂度: O(1)
