导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二

LeetCode-81.Search in Rotated Sorted Array II

题目

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

翻译

33. Search in Rotated Sorted Array的跟进:
如果有重复元素呢?
会对时间复杂度有影响吗?怎样影响以及为什么?
编写函数判断数组中是否存在给定的target。

方法一

遍历……

1
2
3
4
5
6
7
8
public class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
if (nums[i] == target)
return i;
return -1;
}
}

方法二

因为存在重复元素,如在 [1,3,1,1,1] 中查找 3,low=0,high=4,mid=2,nums[low]与nums[mid]相等,但nums[low]
到nums[mid]无序。
这种情况下33题的方法二会出错,因此nums[low]与nums[mid]相等的情况应当单独判断。
因为nums[low] = nums[mid] != target,并且此时无法判断数组的有序状况,所以退化为普通数组查找。所以令low步进即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public boolean search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) return true;
if (nums[low] < nums[mid]) {
if (nums[low] <= target && target < nums[mid]) high = mid - 1;
else low = mid + 1;
} else if (nums[low] > nums[mid]) {
if (nums[mid] < target && target <= nums[high]) low = mid + 1;
else high = mid - 1;
} else low++;
}
return false;
}
}

参考:
http://my.oschina.net/simon203/blog/262523