Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit10306ab

Browse files
committed
feat: add 033
1 parent9ad9da8 commit10306ab

File tree

3 files changed

+92
-0
lines changed

3 files changed

+92
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -63,6 +63,7 @@
6363
|15|[3Sum][015]|Array, Two Pointers|
6464
|17|[Letter Combinations of a Phone Number][017]|String, Backtracking|
6565
|19|[Remove Nth Node From End of List][019]|Linked List, Two Pointers|
66+
|33|[Search in Rotated Sorted Array][033]|Arrays, Binary Search|
6667
|554|[Brick Wall][554]|Hash Table|
6768

6869

@@ -122,6 +123,7 @@
122123
[015]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/015/README.md
123124
[017]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/017/README.md
124125
[019]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md
126+
[033]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/033/README.md
125127
[554]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/554/README.md
126128

127129
[004]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md

‎note/033/README.md

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
#[Search in Rotated Sorted Array][title]
2+
3+
##Description
4+
5+
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
6+
7+
(i.e.,`0 1 2 4 5 6 7` might become`4 5 6 7 0 1 2`).
8+
9+
You are given a target value to search. If found in the array return its index, otherwise return -1.
10+
11+
You may assume no duplicate exists in the array.
12+
13+
**Tags:** Arrays, Binary Search
14+
15+
16+
##思路
17+
18+
题意是让你从一个旋转过后的递增序列中寻找给定值，找到返回索引，找不到返回-1，我们在下面这组数据中寻找规律。
19+
```
20+
1 2 4 5 6 7 0
21+
2 4 5 6 7 0 1
22+
4 5 6 7 0 1 2
23+
5 6 7 0 1 2 4
24+
6 7 0 1 2 4 5
25+
7 0 1 2 4 5 6
26+
```
27+
由于是旋转一次，所以肯定有一半及以上的序列仍然是具有递增性质的，我们观察到如果中间的数比左面的数大的话，那么左半部分序列是递增的，否则右半部分就是递增的，那么我们就可以确定给定值是否在递增序列中，从而决定取舍哪半边。
28+
29+
30+
```java
31+
classSolution {
32+
publicintsearch(int[]nums,inttarget) {
33+
int l=0, r= nums.length-1, mid;
34+
while (l<= r) {
35+
mid= l+ r>>>1;
36+
if (nums[mid]== target)return mid;
37+
elseif (nums[mid]>= nums[l]) {
38+
if (nums[l]<= target&& target< nums[mid]) r= mid-1;
39+
else l= mid+1;
40+
}else {
41+
if (nums[mid]< target&& target<= nums[r]) l= mid+1;
42+
else r= mid-1;
43+
}
44+
}
45+
return-1;
46+
}
47+
}
48+
```
49+
50+
51+
##结语
52+
53+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
54+
55+
56+
57+
[title]:https://leetcode.com/problems/search-in-rotated-sorted-array
58+
[ajl]:https://github.com/Blankj/awesome-java-leetcode
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
packagecom.blankj.medium._033;
2+
3+
/**
4+
* <pre>
5+
* author: Blankj
6+
* blog : http://blankj.com
7+
* time : 2017/10/16
8+
* desc :
9+
* </pre>
10+
*/
11+
publicclassSolution {
12+
publicintsearch(int[]nums,inttarget) {
13+
intl =0,r =nums.length -1,mid;
14+
while (l <=r) {
15+
mid =l +r >>>1;
16+
if (nums[mid] ==target)returnmid;
17+
elseif (nums[mid] >=nums[l]) {
18+
if (nums[l] <=target &&target <nums[mid])r =mid -1;
19+
elsel =mid +1;
20+
}else {
21+
if (nums[mid] <target &&target <=nums[r])l =mid +1;
22+
elser =mid -1;
23+
}
24+
}
25+
return -1;
26+
}
27+
28+
publicstaticvoidmain(String[]args) {
29+
Solutionsolution =newSolution();
30+
System.out.println(solution.search(newint[]{2,1},1));
31+
}
32+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp