LeetCode雙指針：有序數組中的單一元素

題目描述

給你一個僅由整數組成的有序數組，其中每個元素都會出現兩次，唯有一個數只會出現一次。

請你找出并返回只出現一次的那個數。

你設計的解決方案必須滿足 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

解題思路

由有序數組，以及要求 O(log n) 時間復雜度和 O(1) 空間復雜度得知需使用二分查找，怎么找？考慮到它的總數一定是為奇數，那么就可以從左右兩邊每次劃分后的數量進行查找，怎么判別獲得中間值之后知道哪一邊是幾十個哪一邊是偶數個？這個我用的笨方法：舉例

• 1、[1,1,2,3,3,4,4]右指針為6，左指針為0，除以2之后mid為3（奇數）落在第一個3上，根據預想需要調整右指針到第二個3上

• 2、[1,1,2,2,3,3,4]右指針為6，左指針為0，除以2之后mid為3（奇數）落在第二個2上，根據預想需要調整左指針到第一個2上

• 3、[1,2,2,3,3]右指針為4，左指針為0，除以2之后mid為2（偶數）落在第二個2上，根據預想需要調整右指針到第二個2上

• 4、[1,1,2,2,3]右指針為4，左指針為0，除以2之后mid為2（偶數）落在第一個2上，根據預想需要調整左指針到第一個2上

可能此種解釋比較麻煩，我也沒找到讓自己和解的方法，僅代表我自己的理解

接下來就是進行歸類，我把需要移動左指針的進行歸類（1,3）先進行假設：

• 1. 若mid為奇數判斷它和它前一個是否相等，相等則左指針調整
• 2. 若mid為偶數判斷它和它后一個是否相等，相等則左指針調整

帶入2,4情況，發現符合，可以試試找規律，自己推出來較為容易理解，上述也可以不知道這一種選擇，改變判等的位置，相應更改后邊即可

代碼

public class BinSearch3 {public int singleNonDuplicate(int[] nums) {int low = 0, high = nums.length - 1;while (low < high) {int mid = (high - low) / 2 + low;//若mid為偶數判斷它和它后一個是否相等，相等則左指針調整if (mid%2==0){if (nums[mid] == nums[mid + 1]){low = mid + 1;}else {high = mid;}//若mid為奇數判斷它和它前一個是否相等，相等則左指針調整}else {if (nums[mid] == nums[mid - 1]){low = mid + 1;}else {high = mid;}}}return nums[low];}public static void main(String[] args) {BinSearch3 b=new BinSearch3();System.out.println(b.singleNonDuplicate(new int[]{1,1,2,3,3,4,4}));}
}

代碼優化

如上，判定奇偶情況代碼十分臃腫，冗余，對其進行進一步改進，此時需要了解^的使用

位運算的異或操作符 ^。二進制中，異或有一個有趣的性質，即 a ^ b 在 a 和 b 不相同時結果為 1，相同時結果為 0。

1 ^ 3 的結果是 01 ^ 11 = 10，即十進制中的 2。

帶入上述例子[1,1,2,2,3,3,4]mid=3，為奇數將2和1進行異或 01 ^ 11 = 10即十進制中的 2那么不正是相當于對其進行了減一操作

同理，當mid=2時，01 ^ 10 = 11即十進制中的 3那么不正是相當于對其進行了加一操作

因此對其進行優化后：

public class BinSearch3 {public int singleNonDuplicate(int[] nums) {int low = 0, high = nums.length - 1;while (low < high) {int mid = (high - low) / 2 + low;if (nums[mid] == nums[mid ^ 1]) {low = mid + 1;} else {high = mid;}}return nums[low];}public static void main(String[] args) {BinSearch3 b = new BinSearch3();System.out.println(b.singleNonDuplicate(new int[]{1, 1, 2, 3, 3, 4, 4, 8, 8}));}
}