540. 有序数组中的单一元素

2020-05-05

LeetCode

二分查找

3 分钟读完 (大约 421 个字) 0次访问

leetcode 540. 有序数组中的单一元素

题目：540. 有序数组中的单一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例2:

输入: [3,3,7,7,10,11,11]
输出: 10

注意:

您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

方法：二分查找

思路：通过二分查找缩小区间查找，维持mid为奇数，保证0 ~ mid共包含偶数个元素，判断nums[mid]与nums[mid - 1]是否相等，相等则说明前半区间不包含只出现一次的数，将区间往后半区间缩，否则相反，当区间只包含一个元素时，即为结果。

运行数据：执行用时：0 ms，内存消耗：39.4 MB

// LeetCode指定调用方法
public int singleNonDuplicate(int[] nums) {

    // 左右区间范围
    int l = 0;
    int r = nums.length - 1;

    // 二分查找
    while (l < r) { 
        
        // 中间位置
        int mid = (l + r) / 2;

        // 确保mid为奇数，保证0 ~ mid共包含偶数个元素
        if (mid % 2 == 0) {
            mid--;
        }

        // 判断nums[mid]与nums[mid - 1]是否相等，相等则说明前半区间不包含只出现一次的数，将区间往后半区间缩，否则相反
        if (nums[mid] == nums[mid - 1]) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return nums[l];
}