Toc
  1. Problem Description
    1. note
    2. e.g.
  2. Solution
Toc
0 results found
Espada
LeetCode #540 有序数组中的单一元素

Problem Description

给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。

note

您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

e.g.

  • 示例 1:

    输入: [1,1,2,3,3,4,4,8,8]
    输出: 2
  • 示例 2:

    输入: [3,3,7,7,10,11,11]
    输出: 10

Solution

题目简单非常简单,但其中题干中重点强调了O(logn)的时间复杂度和O(1)空间复杂度,所以一切会伴随输入数组大小变化的额外空间和遍历也不行哦,即使是用双指针优化到O(logn/4)也是不满足的。一眼看到O(logn)的时间复杂度就想到了题目的本意应该是让我们利用二分法来解。

因为是有序数组,并且每个元素都是出现两次,除了唯一的一个元素。所以相同的元素一定是连续的并且长度为奇数,所以我们可以每次取中间的元素,和左右两边比较(注意边界),找出相邻元素相同的情况,将整个数组分隔开,左边的子串和右边子串一定有一个是奇数长度(该数组一定有个唯一元素),单个元素就一定藏在这个子串里。

思路

public static int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid - 1 >= 0 && nums[mid] == nums[mid - 1]) {
// 奇数在左边
if (((mid - 1) & 1) == 1) {
right = mid - 2;
} else {
left = mid + 1;
}

} else if (mid + 1 < nums.length && nums[mid] == nums[mid + 1]) {
// 奇数在左边
if ((mid & 1) == 1) {
right = mid - 1;
} else {
left = mid + 2;
}
} else {
return nums[mid];
}
System.out.println("left = " + left);
System.out.println("right = " + right);

}
return 0;
}
龙鸣
"老罗"
本文作者:Espada
版权声明:本文首发于Espada的博客,转载请注明出处!