序数组中的单一元素(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;}
};
更多推荐
[二分法]leetcode540:有序数组中的单一元素(medium)
发布评论