540 Single Element in a Sorted Array

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.和情况一类似，如果nums[mid] == nums[mid + 1] ，判断mid - 1 + 1是否奇数，是的话则答案在[start, mid - 1]之间，否则在[mid + 2, end]之间
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)

483 Smallest Good Base

633 Sum of Square Numbers

Last modified 2yr ago

Copy link

Contents

540. Single Element in a Sorted Array

1. Question

2. Implementation

3. Time & Space Complexity

540. Single Element in a Sorted Array​

1. Question

2. Implementation

3. Time & Space Complexity

540. Single Element in a Sorted Array