来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array

题目描述

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

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

示例 2:

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

提示:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

解题思路

本题难点在于限制了时间复杂度和空间复杂度，根据时间复杂度来看，很明显在诱导解题者使用二分法解题。

首先寻找规律，单一元素a的左边必然有偶数个元素，所以a的坐标必然是偶数，并且，a左边偶数坐标left的值均与left+1的值相同，右边偶数坐标right的值与right-1的值相同，所以，只需要找到这个分界点就是单一元素。

使用二分法，左边界left设置为0，右边界right设置为最大的偶数坐标，求出中间的偶数坐标mid（如果是奇数需要-1变成偶数坐标）判断是否nums[mid] == nums[mid + 1],如果相同，则a在mid的右边，并且mid不可能为单一元素，将left设置为mid + 2；否则，a可能在mid左边，也可能就是mid，所以将right设置为mid。

代码展示

class Solution {

public:

    int singleNonDuplicate(vector<int>& nums) {

        int iLeft = 0, iRight = nums.size() - 1, iMid = 0;

        if(iRight % 2)

            iRight--;

        while(iLeft < iRight)

        {

            iMid = (iLeft + iRight) / 2;

            if(iMid % 2)

                iMid --;

            if(nums[iMid] == nums[iMid + 1])

                iLeft = iMid + 2;

            else

                iRight = iMid;

        }

        return nums[iLeft];

    }

};

巴特西

LeetCode-540 有序数组中单一元素

题目描述

解题思路

代码展示

运行结果

最新文章

热门文章