p81

发表于 | 分类于 |

LeetCode 81 Search in Rotated Sorted Array II 题解

1.题目：

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.

题意：

在一个被扭转的有序数组里查找一个数是否存在（可能有重复的数）

2.解题思路:

重复的数会干扰判断，如果头尾重合拿出来单独讨论了TUT，应该有更快的做法。

3.代码

[title] [] [url] [link text]
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
39
40
41
42
43
44
45
 

public class Solution {
    public boolean search(int[] nums, int target) {
        int s = 0;
		int e = nums.length - 1;
		while (s <= e) {
			int mid = (s + e) / 2;
			if (nums[mid] == target)
				return true;

			if (nums[s] <= nums[mid]) {// 前部分全是有序的
				if (nums[s] == nums[mid]) {
					while (s < mid) {
						if (nums[s] == target)
							return true;
						//System.out.println(s);
						s++;
					}
				}
				if (target < nums[mid] && target >= nums[s])
					e = mid - 1;
				else
					s = mid + 1;
			}

			if (nums[mid] <= nums[e]) {// 后部分全是有序的
				if (nums[e] == nums[mid]) {
					while (e > mid) {
						if (nums[e] == target)
							return true;
						//System.out.println(s);
						e--;
					}
				}
				if (target > nums[mid] && target <= nums[e])
					s = mid + 1;
				else
					e = mid - 1;
			}
		}
		return false;
    }
}

4.一些总结：