540. Single Element in a Sorted Array

发表于 | 分类于

每日一题 2019 - 02 - 26

题目：

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

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

Example 2:

1
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(logn)的时间复杂度找出给定数组中的不成对的元素，从时间复杂度上可以选择使用二分查找的方法来完成任务。

具体的查找可以以二分查找为主线，在查找时候我们在找到中间元素之后，我们可能需要进行分类，设中间元素为mid，那么

  • 如果 arr[mid] ！= arr[mid-1]，那就证明中位值跟中位值前面一位数字不是一对，所以就要把mid往前推一位，保证二分查找时候不会出错
  • 根据mid进行划分之后，我们会发现mid前后两部分奇偶性不同，那么很明显要找的数据就在处于奇数长度的序列中，接着就剪短二分查找的长度，继续查找。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        while (r != l)
        {
            int mid = (l + r) / 2;
            if (nums[mid] != nums[mid - 1])
            {
                mid = mid - 1;
            }
            if ((mid + 1) % 2 == 0)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return nums[l];
    }
};
0%
undefined