540 Single Element in a Sorted Array

1. Question

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
Example 1:
1
Input: [1,1,2,3,3,4,4,8,8]
2
3
Output: 2
Copied!
Example 2:
1
Input: [3,3,7,7,10,11,11]
2
3
Output: 10
Copied!
Note:Your solution should run in O(log n) time and O(1) space.

2. Implementation

(1) Binary Search
思路:用二分法的思想,中点mid,有三种情况 1. 如果nums[mid - 1] == nums[mid], 判断mid - 2 + 1(因为数组从0开始)是否奇数,如果是,则出现一次的数在[start, mid - 2]之间,否则在[mid + 1, end]之间
  1. 1.
    和情况一类似,如果nums[mid] == nums[mid + 1] ,判断mid - 1 + 1是否奇数,是的话则答案在[start, mid - 1]之间,否则在[mid + 2, end]之间
  2. 2.
    情况三,当nums[mid] != nums[mid - 1] 且 nums[mid] != nums[mid + 1]时,nums[mid]就是我们要找的数
1
public class Solution {
2
public int singleNonDuplicate(int[] nums) {
3
if (nums == null || nums.length <= 2) {
4
return -1;
5
}
6
7
int start = 0, end = nums.length - 1, mid = 0;
8
9
while (start + 1 < end) {
10
mid = start + (end - start) / 2;
11
12
if (nums[mid - 1] == nums[mid]) {
13
if ((mid - 2 + 1) % 2 != 0) {
14
end = mid - 2;
15
}
16
else {
17
start = mid + 1;
18
}
19
}
20
else if (nums[mid] == nums[mid + 1]) {
21
if ((mid - 1 + 1) % 2 != 0) {
22
end = mid - 1;
23
}
24
else {
25
start = mid + 2;
26
}
27
}
28
else {
29
return nums[mid];
30
}
31
}
32
33
if (start > 0 && nums[start - 1] != nums[start]) {
34
return nums[start];
35
}
36
else {
37
return nums[end];
38
}
39
}
40
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(logn), 空间复杂度O(1)