05 August 2008
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 1
[0,0,1,2,2,5,6]
1
[2,5,6,0,0,1,2]
You are given a target value to search. If found in the array return 1
true
1
false
Example 1:
1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
1
2
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
1
nums
和上一道题33 - Search in Rotated Sorted Array区别是这道题目中元素会有重复的情况出现，找到了就返回true，没找到返回false。题目中问到了是否影响复杂度，因为重复元素这个条件的出现，出现了比较复杂的cases，影响了算法的时间复杂度。前一道题是依靠中间和边缘元素的大小关系，来判断哪一半是不受rotate影响仍然有序的；而现在因为重复元素的出现，如果我们遇到中间和边缘相等的情况，我们就无法判断哪边有序，因为两边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。
解决的办法只能是对边缘移动一步（跟154 - Find Minimum in Rotated Array II，当中间等于右边的数时，无法判断最小数在左边还是右边，只能移动一步的情况，有异曲同工的地方），直到边缘和中间不再相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而它就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[mid] > nums[left]) { // 左侧有序
if (nums[left] <= target && nums[mid] > target) { // 在有序部分
right = mid;
} else { // 在乱序部分
left = mid;
}
} else if (nums[mid] < nums[right]) {// 右侧有序
if (nums[mid] < target && nums[right] >= target) {//在有序部分
left = mid;
} else {// 在乱序部分
right = mid;
}
} else { // nums[mid]和nums[left]以及nums[right]的关系无法判断大小
if (nums[left] == target) {
return true;
} else {
left++; //只能从左到右排除一个元素
}
}
}
if (nums[left] == target || nums[right] == target) {
return true;
}
return false;
}
}
不过既然时间复杂度反正已经是O(n)了，那我们也可以不用Binary Search，直接从左到右扫一遍了事，当然面试中应该先分析上面的情况再说这个办法，如果没有交流直接就这样写的话，估计下一道题面试官直接难题伺候了。
1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean search(int[] nums, int target) {
for(int i = 0;i < nums.length; i++){
if(nums[i] == target){
return true;
}
}
return false;
}
}