yoruru的努力日記

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

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

SOL：

大概花了10分鐘想出完整的解法。

一樣用 binary search，首先判斷抓到的 M 是跟前一個元素一組或跟下一個元素一組。

若都沒有人跟他一樣，就找到答案了。

接著判斷除了M那一組以外的個數。

左右半邊哪一邊的個數是奇數就search那一邊。

參考花花的解法，發現他的程式碼更簡潔一些，直接以M是奇數還偶數，就可以判斷答案在M之前還是M之後。

用 M xor 1 (M^1)的寫法，來描述 若M是奇數則跟前一個元素一組，若M是偶數則跟下一個元素一組，超酷！

若不相等，要嘛是找到答案，要嘛是前面有答案，所以搜尋左半邊。

若是相等，則前面的數字們都沒有問題，直接搜尋右半邊。

然後 xor(異或) 的寫法我花了一段時間才理解。

XOR的真值表如下，^1會讓原本0->1、1->0。

舉例說明一下M^1：

當M為偶數，二進位的最後一位0^1會變1，所以會變成M+1。

ex. 2(10)^1=3(11)、4(100)^1=5(101)

當M為奇數，二進位的最後一位1^1會變0，所以會變成M-1。

ex. 1^1=0、3(11)^1=2(10)

Reference：

1. LeetCode-540. Single Element in a Sorted Array

2. 花花酱 LeetCode 540. Single Element in a Sorted Array

3. Find the element that appears once in a sorted array | GeeksforGeeks

4. XOR 加密简介

5. Python xor 運算子用法與範例