[LeetCode] 540. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

有序数组中的单一元素。

题意是给一个排好序的数组，所有的元素都成对出现，请你找出唯一的单独元素。有时间复杂度O(log n)的要求。既然是这个要求，所以一定是二分法做。注意到 input 有一个现象，就是落单的元素的 index 一定是偶数，所以我给出的二分法做了一点变化，end 只取了数组长度的一半，但是在找 mid 的时候我再乘以2，这样保证了 mid 一定是偶数。如果 nums[2 * mid] != nums[2 * mid + 1] ，那么说明单独的元素一定在前半段，否则就在后半段。这个题的官方题解写的很详细，我参考了方法三。

时间O(logn)

空间O(1)

Java实现

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length / 2;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[2 * mid] != nums[2 * mid + 1]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return nums[2 * start];
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function(nums) {
    let start = 0;
    let end = nums.length / 2;
    while (start < end) {
        let mid = Math.floor((start + end) / 2);
        if (nums[mid * 2] != nums[mid * 2 + 1]) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    return nums[start * 2]
};

二刷的时候我写了一个比较常规的二分法，因为第一种做法面试的时候除非遇到原题否则不太容易想得到。常规的二分法的右边界是 end = nums.length - 1，当 mid 是奇数的时候，我们会通过对其减一，强行让其变成偶数，这样如果 nums[mid] == nums[mid + 1] 的话，说明单一元素还在右边，要 start = mid + 2。这里 mid + 2 的原因在于 mid 和 mid + 1 背后指向的元素是相等的。因为会涉及到 mid + 2 的操作，所以第五行的 while 判断是 start < end 而不是 start <= end，这一点跟模板有区别。

Java实现

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            // 强行把mid变为偶数，因为落单的数字只会在偶数index上
            if (mid % 2 == 1) {
                mid--;
            }
            if (nums[mid] == nums[mid + 1]) {
                start = mid + 2;
            } else {
                end = mid - 1;
            }
        }
        return nums[start];
    }
}

LeetCode 题目总结