LeetCode 540 Single Element in a Sorted Array

思路

由于时间复杂度上有要求，所以比较容易想到二分查找。但是此题的二分前进方向不是很明显。如下面的例子：
1 2 2 3 3
1 1 2 2 3
可以看出，落单者在mid后面是奇数位=偶数位，落单着在mid前面是偶数位=奇数位。由此可以得出二分的走向。

复杂度

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

代码

class Solution {
    public int singleNonDuplicate(int[] nums) {
    int start = 0, end = nums.length-1;// 保证了mid不为0while(start + 1 < end) {
    int mid = start + (end-start)/2;if(nums[mid-1] < nums[mid] && nums[mid] < nums[mid+1]) {
    return nums[mid];}if(mid % 2 == 0) {
    if(nums[mid] == nums[mid+1]) {
    start = mid;} else {
    end = mid;}} else {
    if(nums[mid] == nums[mid+1]) {
    end = mid;} else {
    start = mid;}}}if(start == 0 && nums[start] != nums[end])return nums[start];else if(end == nums.length-1 && nums[start] != nums[end])return nums[end];else if(nums[start] == nums[start-1])return nums[end];elsereturn nums[start];}
}

Follow up

如果数组没排序的话怎么做？