1. 題目

給定一個只包含整數的有序數組，每個元素都會出現兩次，唯有一個數只會出現一次，找出這個數。

示例 1: 輸入: [1,1,2,3,3,4,4,8,8] 輸出: 2示例 2: 輸入: [3,3,7,7,10,11,11] 輸出: 10

注意: 您的方案應該在 O(log n) 時間復雜度 和 O(1)空間復雜度中運行。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 O(n) 位運算解法

• 一個數與自己 異或^ 等0
• 0^n = n

class Solution { public:int singleNonDuplicate(vector<int>& nums) {int ans = 0;for(int i = 0; i < nums.size(); ++i)ans ^= nums[i];return ans;} };

2.2 遞歸查找

最壞O(n)時間復雜度

class Solution {bool found = false;int ans; public:int singleNonDuplicate(vector<int>& nums) {if(nums.size()==1)return nums[0];find(nums,0,nums.size()-1);return ans;}void find(vector<int>& nums, int l, int r){if(found || l > r)return;int mid = l+((r-l)>>1);if((mid == 0 && nums[mid] != nums[mid+1])|| (mid == nums.size()-1 && nums[mid-1] != nums[mid])){found = true;ans = nums[mid];}else if(nums[mid] != nums[mid+1] && nums[mid] != nums[mid-1]){found = true;ans = nums[mid];}else{find(nums,l,mid-1);find(nums,mid+1,r);}} };

2.3 二分查找

看見題目要求的時間復雜度是 O（lg n），且有序，應該很容易想到二分法

• 答案一定在切分的個數為奇數個的那一邊

class Solution { public:int singleNonDuplicate(vector<int>& nums) {int l = 0, r = nums.size()-1, mid;while(l < r) {mid = l+((r-l)>>1);if(mid % 2) //奇數，1，奇數{if(nums[mid] == nums[mid+1])r = mid-1;elsel = mid+1;} else // 偶數個，1，偶數個{if(nums[mid] == nums[mid+1])l = mid+2;elser = mid;}}return nums[l];} };

總結

以上是生活随笔為你收集整理的LeetCode 540. 有序数组中的单一元素（位运算二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。