[二分法]leetcode540：有序数组中的单一元素(medium)

序数组中的单一元素(medium)"/>

[二分法]leetcode540：有序数组中的单一元素(medium)

题目：

题解：

• 二分法
• 由于本题数组长度为奇数，并且我们想要找到单一元素的话，每次二分区间也只能在长度为奇数的子数组查找，所以mid每次都能将数组分成长度相等的子数组，分为以下2大情况（4小情况）来讨论：

---

• 1）若num[mid]==nums[mid+1]表示中间元素的相同元素在右边，我们可根据左右子数组的长度来确定下次搜索区间：
• • 1.1）左右子数组长度为偶数时，那么我们在右子数组中寻找单一元素，因为右子数组长度为偶数，我们减去nums[mid+1]之后，右子数组长度为奇数了，那么单一元素必然存在其中，下次更新l=mid+2。
    
• • 1.2）左右子数组长度为奇数时，那么我们在左子数组中寻找单一元素，因为nums[mid+1]在右子数组中，右子树组减去nums[mid+1]后，右子树长度为偶数，单一元素必然不存在于右子数组中，只有存在于左子数组中，下次更新r=mid-1。
    

---

• 2）若nums[mid]=nums[mid-1]表示中间元素的相同元素在左边，我们可根据左右子数组的长度来确定下次搜索区间：
• • 2.1）左右子数组长度为偶数时，那么我们在左子数组中寻找单一元素，因为左子数组长度为偶数，我们减去nums[mid-1]之后，右子数组长度为奇数了，那么单一元素必然存在其中，下次更新r=mid-2。
• • 2.2）左右子数组长度为奇数时，那么我们在右子数组中寻找单一元素，因为nums[mid-1]在左子数组中，左子数组减去nums[mid-1]后，左子数组的长度为偶数，单一元素必然不存在于左子数组中，只有存在于右子数组中，下次更新l=mid+1。
    

代码如下：

class Solution {
public:// 题解1：二分法，时间复杂度O(logn)，空间复杂度O(1)int singleNonDuplicate_1(vector<int>& nums) {int l=0,r=nums.size()-1;while(l<r){int mid=l+r>>1;// flag用来表示mid左右数组是否为偶数，true表示是，false则不是bool flag=(r-mid)%2==0;// mid的相同元素落在右边if(nums[mid]==nums[mid+1]){// 左右子数组长度为偶数，则在右子数组寻找；否则在左子数组寻找if(flag)l=mid+2;else r=mid-1;}// mid的相同元组落在左边else if(nums[mid]==nums[mid-1]){// 左右子数组长度为偶数，则左子数组寻找；否则在右子树组寻找if(flag)r=mid-2;else l=mid+1;}// 找到单一元素else{return nums[mid];}}// 区间中最后一个值为单一元素return nums[l];}  // 题解2：一次遍历，时间复杂度O(n)，空间复杂度O(1)int singleNonDuplicate_2(vector<int>& nums){for(int i=0;i<nums.size()-1;i+=2){if(nums[i]!=nums[i+1])return nums[i];}// 单一元素在数组尾部return nums.back();} // 题解3：异或，a^a=0,b^0=bint singleNonDuplicate(vector<int>& nums){int res=0;for(int i=0;i<nums.size();++i)res^=nums[i];return res;}
};