540. 有序数组中的单一元素

540. 有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 $O(logn)$ 时间复杂度和 $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<=10^5$
$0<=nums[i]<=10^5$

思路：（二分查找）

• 只出现一次的元素所在下标 x 一定是偶数，可以在偶数下标范围内二分查找;
• 由于只出现一次的元素所在下标 x 的左边有偶数个元素，且都满足$nums[loc]==nums[loc+1]$，所以当满足$nums[loc]=nums[loc+1]$时，该元素一定在右边，则 $l=m+1$;
• 满足$nums[loc]!=nums[loc+1]$，则该元素可能就是在本坐标，或者是左边，令$ h = m$ ;
• 直到$l == h $时，找到本元素的下标

代码：（Java）

public class Single_element {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int [] nums = {1,1,2,3,3,4,4,8,8};
		System.out.println(singleNonDuplicate(nums));
	}
	 public static int singleNonDuplicate(int[] nums) {
		 int l = 0, h = nums.length/2;
		 while(l < h) {
			 int m = l + (h - l) / 2;
			 int loc = m * 2;
			 if(nums[loc] == nums[loc + 1]) {
				 l = m + 1;
			 }else {
				 h = m;
			 }
		 }
		 return nums[2 * l];
	 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析：

• 时间复杂度：$O(logn)$，其中 $n$ 是数组 $nums$ 的长度。需要在偶数下标范围内二分查找，二分查找的时间复杂度是 $O(logn)$。

• 空间复杂度：$O(1)$。

注：仅供学习参考

来源：力扣