leetcode链接：
https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
方案一
二分法，设置一个标志位判断target 在数组的前半部分还是后半部分。
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
| int left = 0,
right = nums.length,
mid = 0,
start = nums[0],
flag = 0;
if (target < start)
flag = 1;
while (left < right) {
mid = left + (right - left) / 2;
if (flag == 0 ) {
if (nums[mid] < start || nums[mid] > target) {
right = mid;
} else if (nums[mid] == target) {
return mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] > start || nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] == target) {
return mid;
} else {
right = mid;
}
}
}
return -1;
|
结果
- 195/195 cases passed (0 ms)
- Your runtime beats 100 % of java submissions
- Your memory usage beats 44.4 % of java submissions (41.1 MB)
分析
时间复杂度：
O( log n )
空间复杂度：
O( 1 )
与官方方案类似
几乎最优方案
https://leetcode.cn/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
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
| class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
作者：LeetCode-Solution
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|