【LeetCode】 540. Single Element in a Sorted Array

Description

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Note: Your solution should run in O(log n) time and O(1) space.

給你一個整理過的陣列，其元素只包含出現兩次的整數和只有一個只出現一次的整數。找到那個單獨只出現一次的元素。

注意：
你的答案應該在O(log n)的時間複雜度和O(1)的空間複雜度之中。

Example:

Example 1:

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


Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Solution

• 可以先看看這題，比較一下兩題的差異：
  • 本題有排序過
  • 本題時間複雜度需求拉到O(log n)
• 而從排序過和O(log n)就應該很直覺地想到二分搜尋法。

---

• 我們可以將情況分為幾種情形：
  1. 中間數剛好就是目標
  2. 中間數不是目標
     1. 中間數的左/右分別有奇數個數字
        1. 中間數和前面的數字一樣
        2. 中間數和後面的數字一樣
     2. 中間數的左/右分別有偶數個數字
        1. 中間數和前面的數字一樣
        2. 中間數和後面的數字一樣
• 基本上從範例測資就可以想出並列出上面的這些情形，至於為什麼要考慮到奇數偶數呢？
  • 那是為了確保新的範圍總個數為奇數，如果不是奇數就無法判斷誰是單獨的了。
• 接著就從範例中分析出新的範圍應該取哪裡(有些需要包含中間數，有些不用)，最後再加上終止條件起始等於終點即可。

Code

class Solution {
public:
    int find(vector<int>& nums, int s, int e)
    {
        if(s == e)
            return nums[s];
        int mid = (s + e) / 2;
        if(nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1])
            return nums[mid];
        
        int n = (e - s) / 2; 
        if(n % 2 == 0)
        {
            if(nums[mid] == nums[mid - 1])
            {
                return find(nums, s, mid);
            }
            else
            {
                return find(nums, mid, e);
            }
        }
        else
        {
            if(nums[mid] == nums[mid - 1])
            {
                return find(nums, mid + 1, e);
            }
            else
            {
                return find(nums, s, mid - 1);
            }
        }
    }
    int singleNonDuplicate(vector<int>& nums) {
        return find(nums, 0, nums.size() - 1);
    }
};

tags: LeetCode C++