KK's blog

每天积累多一些

0%

LeetCode 540 Single Element in a Sorted Array

Posted on Edited on Disqus:

LeetCode 540 Single Element in a Sorted Array

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1: 

**Input:** [1,1,2,3,3,4,4,8,8]
**Output:** 2

Example 2: 

**Input:** [3,3,7,7,10,11,11]
**Output:** 10

Note: Your solution should run in O(log n) time and O(1) space.

题目大意：

一个有序数组中，每个数字都出现了两次，只有一个数字出现了一次，求出现一次的数字。

解题思路：

这是A公司Problem solving的题目。类似于L136。此题数组有序且要求O(logn)时间，所以考虑用二分法。由于没有输入tgt，有点似
算法文档中用二分法求峰值，就是比较相邻两个数做二分法。考虑一个结论，若数组为偶数个数，就一定不存在只出现一次的元素。
所以必须考虑奇偶位，若下标mid为偶数，其后一位与其相等，就一定在右半边搜索left=mid+2(不会是mid和mid+1)，如第二个
例子，因为mid左边个数为偶数，利用结论可知不会在左边。同理与后一位不等，搜左边right=mid(可能为mid)。注意边界。
若mid为奇数，mid前面有奇数个，mid包括自己的后面有偶数个，所以mid和mid+1上的数相等，就应在左半搜，所以与偶数位的
情况正好相反，但是边界不同，产生了4个if语句。
法二：改进一下，若mid为奇数位，就mid–归结为偶数位的情况，这样if变成两个。

注意事项：

  1. 类似于Leetcode 033，四种情况，前两种中的第二种全包第一种。
  2. for循环后，答案一定在start和end其中一个。end前面有偶数个与start不同就肯定在start上。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def singleNonDuplicate(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) //2
		if mid % 2 == 1 and mid >= 1 and nums[mid - 1] == nums[mid]:
			start = mid
		elif mid % 2 == 1:
			end = mid
		elif mid % 2 == 0 and mid >= 1 and nums[mid - 1] != nums[mid]:
			start = mid
		else:
			end = mid
	if end % 2 == 1 and nums[start] != nums[end]:
		return nums[start] # remember
	else:
		return nums[end]

注意事项：

  1. 边界也就是mid的赋值，写出例子来理解。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int singleNonDuplicate(int[] nums) {
	int N = nums.length;
	int left = 0, right = N - 1;
	while (left < right) {
		int mid = (right - left) / 2 + left;
		boolean isEven = true;
		if (mid % 2 == 1) isEven = false;
		if ((isEven && nums[mid] != nums[mid + 1]) )
			right = mid;
		else if (isEven && nums[mid] == nums[mid + 1])
			left = mid + 2;
		else if (!isEven && nums[mid] == nums[mid + 1])
			right = mid-1;
		else
			left = mid + 1;
	}
	return nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
public int singleNonDuplicate2(int[] nums) {
	  int N = nums.length;
	  int left = 0, right = N - 1;
	  while (left < right) {
		  int mid = (right - left) / 2 + left;
		  if (mid % 2 == 1) mid--;
		  if (nums[mid] != nums[mid + 1])
			  right = mid;
		  else
			  left = mid + 2;
	  }
	  return nums[left];
}

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)。

Follow-up:

首先问L316 Given a non-empty array of integers, every element appears twice except for one. Find that single one.
XOR解法，不用实现。
Follow up问题是L260 Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
分三步。若只有一个数出现1次，只要把所有数异或^即可(相同数异或=0)。如果有两个此数，异或结果是这两数不同的位。只要选为1且最低位(或任意为1的位)lowBit=a-(a&(a-1))。再扫所有数，根据它们在lowBit上=0和=1分组异或num1, num2，最后分组异或后它们为所求

Free mock interview