一起学算法-540. 有序数组中的单一元素

一、题目

LeetCode-540. 有序数组中的单一元素
地址：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

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

示例 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)空间复杂度中运行。

二、解题思路

本题要求O(log n)时间复杂度，很明显不能用暴力法，只能用二分查找。
我们首先将left和 right 指向数组首尾两个元素。然后进行二分搜索将数组搜索空间减半，直到找到单一元素（该元素与左右两边的都不相等）或者只有一个元素为止。
搜索空间减半，如何将数组减半呢，我们很容易发现，单元素所在区间个数是奇数。
例如:
[1,1,2,3,3,4,4,5,5]
[1,1,2,2,3,3,4]
因此，我们可以通过判断以nums[mid]，区分的两个区间的元素个数的奇偶来使得，搜索空间减半。

三、实现过程

c++

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            bool flag = (right - mid) % 2 == 0; 
            if(nums[mid-1] == nums[mid]){
                if(flag){
                    right = mid -2;
                }else{
                    left = mid + 1;
                }
            }else if(nums[mid+1] == nums[mid]){
                if(flag){
                    left = mid + 2;
                }else{
                    right = mid - 1;
                }
            }else{
                //单元素
                return nums[mid];
            }
        }
        return nums[left];
    }
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNonDuplicate($nums) {
        $left = 0;
        $right = count($nums) - 1;
        while($left < $right){
            $mid = (int)($left + ($right - $left)/2);
            $flag = ($right - $mid) % 2 == 0; 
            if($nums[$mid-1] == $nums[$mid]){
                if($flag){
                    $right = $mid -2;
                }else{
                    $left = $mid + 1;
                }
            }else if($nums[$mid+1] == $nums[$mid]){
                if($flag){
                    $left = $mid + 2;
                }else{
                    $right = $mid - 1;
                }
            }else{
                return $nums[$mid];
            }
        }
        return $nums[$left];
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function(nums) {
        var left = 0,right = nums.length - 1,mid;
        while(left < right){
            mid = Math.floor(left + (right - left)/2);
            var flag = (right - mid) % 2 == 0; 
            if(nums[mid-1] == nums[mid]){
                if(flag){
                    right = mid -2;
                }else{
                    left = mid + 1;
                }
            }else if(nums[mid+1] == nums[mid]){
                if(flag){
                    left = mid + 2;
                }else{
                    right = mid - 1;
                }
            }else{
                return nums[mid];
            }
        }
        return nums[right];
};

四、小结

二分查找的基本思想并不能，难点在于如何找到合适的条件来使区间减半。

分享不易，如果你觉得还有用就点个赞再走吧！