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

Commit22cbf1a

Browse files
committed
find
1 parent2198d4e commit22cbf1a

File tree

3 files changed

+94
-1
lines changed

3 files changed

+94
-1
lines changed

‎binarySearch/FindMin.java

Lines changed: 38 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
packageAlgorithms.binarySearch;
2+
23
publicclassFindMin {
3-
publicintfindMin(int[]num) {
4+
// Solution 1:
5+
publicintfindMin1(int[]num) {
46
if (num ==null ||num.length ==0) {
57
return0;
68
}
@@ -38,4 +40,39 @@ public int findMin(int[] num) {
3840

3941
return0;
4042
}
43+
44+
// solution 2:
45+
publicintfindMin(int[]A) {
46+
if (A ==null ||A.length ==0) {
47+
return0;
48+
}
49+
50+
if (A.length ==1) {
51+
returnA[0];
52+
}elseif (A.length ==2) {
53+
returnMath.min(A[0],A[1]);
54+
}
55+
56+
// 至少有3个元素，才有讨论的价值
57+
intl =0;
58+
intr =A.length -1;
59+
60+
while (l <r -1) {
61+
intm =l + (r -l) /2;
62+
63+
// means that there is no rotate.
64+
if (A[r] >A[l]) {
65+
returnA[0];
66+
}
67+
68+
// left side is sorted.
69+
if (A[m] >A[l]) {
70+
l =m;
71+
}else {
72+
r =m;
73+
}
74+
}
75+
76+
returnA[r];
77+
}
4178
}

‎binarySearch/FindMin2.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
packageAlgorithms.binarySearch;
2+
3+
4+
/*
5+
* Find Minimum in Rotated Sorted Array II Total Accepted: 2541 Total Submissions: 9558 My Submissions Question Solution
6+
Follow up for "Find Minimum in Rotated Sorted Array":
7+
What if duplicates are allowed?
8+
9+
Would this affect the run-time complexity? How and why?
10+
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
11+
12+
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
13+
14+
Find the minimum element.
15+
16+
The array may contain duplicates.
17+
* */
18+
publicclassFindMin2 {
19+
publicintfindMin(int[]num) {
20+
if (num ==null ||num.length ==0) {
21+
return0;
22+
}
23+
24+
intlen =num.length;
25+
if (len ==1) {
26+
returnnum[0];
27+
}elseif (len ==2) {
28+
returnMath.min(num[0],num[1]);
29+
}
30+
31+
intleft =0;
32+
intright =len -1;
33+
34+
while (left <right -1) {
35+
intmid =left + (right -left) /2;
36+
// In this case, the array is sorted.
37+
// 这一句很重要，因为我们移除一些元素后，可能会使整个数组变得有序...
38+
if (num[left] <num[right]) {
39+
returnnum[left];
40+
}
41+
42+
// left side is sorted. CUT the left side.
43+
if (num[mid] >num[left]) {
44+
left =mid;
45+
// left side is unsorted, right side is sorted. CUT the right side.
46+
}elseif (num[mid] <num[left]) {
47+
right =mid;
48+
}else {
49+
left++;
50+
}
51+
}
52+
53+
returnMath.min(num[left],num[right]);
54+
}
55+
}

‎dp/Candy.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,3 +31,4 @@ public int candy(int[] ratings) {
3131
returnsum;
3232
}
3333
}
34+

0 commit comments

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