欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-17 17:14:28
...

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

1.题目描述

给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。
示例 1:
540. 有序数组中的单一元素
示例 2:
540. 有序数组中的单一元素
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

2.思路(二分法)

  1.令 index 为 Single Element 在数组中的位置。在 index 之后,数组中原来存在的成对状态被改变。如果 mid = left + (right - left) / 2 为偶数,并且 mid + 1 < index,那么 nums[mid] == nums[mid + 1];如果m + 1 >= index,那么 nums[mid] != nums[mid + 1]。
  2.所以,如果 nums[mid] == nums[mid + 1],那么 index 所在的数组位置为 [mid + 2, right],此时令 left = mid + 2;如果 nums[mid] != nums[mid + 1],那么 index 所在的数组位置为 [left, mid],此时令 right = mid。
  3.一旦 left == right,则当前搜索空间为 1 个元素,那么该元素为单个元素,我们将返回它。

3.代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(mid % 2 == 1){//保证m为偶数
                mid--;
            }
            if(nums[mid] == nums[mid+1]){//说明nums[mid]在目标的右边
                left = mid + 2;
            }
            else{
                right = mid;//说明nums[mid]在目标的左边
            }
        }
        return nums[left];
    }
};

4.复杂度分析

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