给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足
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提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
思路
题目要求时间复杂度在log n,也就是说不能遍历全部的数字
除了我们要求出的数字以外,其他都是成对出现的,并且该数组是有序的,与之相等的数组不是在它左边就是在它右边
同时如果我们把数组分割成两段来看,答案数字肯定只会出现在一边,并且出现单个数字的那边的数字个数肯定是奇数,所以我们就可以考虑二分了
下面是题目样例中的示意图,单个数字所在的那一边一定是奇数个数字
每次取中点的数看是和它右边的相等还是和它左边的相等
如果都不想等那么这就是要找的数
如果相等,判断对应的那边剩下的数字是否是成对的 成对则单个数字肯定在另一边,如果不是成对的那么肯定就在判断的这一边,同时缩小边界
Code
class Solution {
public int singleNonDuplicate(int[] nums) {
int n=nums.length;
int i=0,j=n-1;
while(i<=j){
int mid=(i+j)/2;
//右
if(mid+1<n&&nums[mid+1]==nums[mid]){
int len=n-mid-2;//右边还剩几个元素
if(len%2==0){
j=mid-1;
}else{
i=mid+1;
}
}
else //左
if(mid-1>=0&&nums[mid-1]==nums[mid]){
int len=mid-1;//左边还剩几个元素
if(len%2==0){
i=mid+1;
}else{
j=mid-1;
}
}else
return nums[mid];
}
return 1;
}
}