8000 add 153 solution · dj7777/awesome-golang-leetcode@8001df3 · GitHub
[go: up one dir, main page]
Skip to content

Commit 8001df3

Browse files
6boris6boris
committed
add 153 solution
1 parent 2295eaa commit 8001df3

File tree

3 files changed

+135
-0
lines changed

3 files changed

+135
-0
lines changed

‎src/0153.Find-Minimum-in-Rotated-Sorted-Array/README.md

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
# [153. Find Minimum 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+
Find the minimum element.
10+
11+
You may assume no duplicate exists in the array.
12+
**Example 1:**
13+
14+
```
15+
Input: [3,4,5,1,2]
16+
Output: 1
17+
```
18+
19+
**Example 2:**
20+
21+
```
22+
Input: [4,5,6,7,0,1,2]
23+
Output: 0
24+
```
< 8000 /code>25+
26+
**Tags:** Math, String
27+
28+
## 题意
29+
> 现有一个有序数组，假设从某个数开始将它后面的数按顺序放到了数组前面。
30+
(即 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2])。
31+
请找出数组中的最小元素。
32+
数组中不包含重复元素。
33+
>
34+
>
35+
## 题解
36+
37+
### 思路1
38+
> (二分) O(logn)
39+
40+
处理这种问题有个常用技巧：如果不想处理边界情况，比如当数组只有两三个数的时候，代码会出问题。我们可以在数组长度太短(这道题中我们判断数组长度小于5)时，直接暴力循环做；数组有一定长度时再用二分做。
41+
这样做并不会影响算法的时间复杂度，但会缩短写代码的时间。
42+
为了便于理解，我们将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：
43+
44+
![](https://oss.kyle.link/leetcode/leetcode-153.png)
45+
46+
我们会发现数组中最小值前面的数 nums[i]nums[i] 都满足：nums[i]≥nums[0]nums[i]≥nums[0]，其中 nums[n−1]nums[n−1] 是数组最后一个元素；而数组中最小值后面的数（包括最小值）都不满足这个条件。
47+
所以我们可以二分出最小值的位置。
48+
另外，不要忘记处理数组完全单调的特殊情况。
49+
时间复杂度分析：二分查找，所以时间复杂度是 O(logn)O(logn)。
50+
51+
```go
52+
func findMin(nums []int) int {
53+
if nums[len(nums)-1] > nums[0] {
54+
return nums[0]
55+
}
56+
l, r := 0, len(nums)-1
57+
for l < r {
58+
mid := l + (r-l)>>1
59+
if nums[mid] >= nums[0] {
60+
l = mid + 1
61+
} else {
62+
r = mid
63+
}
64+
}
65+
66+
return nums[l]
67+
}
68+
```
69+
70+
71+
## 结语
72+
73+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
74+
75+
[title]: https://leetcode.com/problems/two-sum/description/
76+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0153.Find-Minimum-in-Rotated-Sorted-Array/Solution.go

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package Solution
2+
3+
func findMin(nums []int) int {
4+
if nums[len(nums)-1] > nums[0] {
5+
return nums[0]
6+
}
7+
l, r := 0, len(nums)-1
8+
for l < r {
9+
mid := l + (r-l)>>1
10+
// 数组中最小的元素会小于第一个元素
11+
if nums[mid] >= < 8000 span class=pl-s1>nums[0] {
12+
l = mid + 1
13+
} else {
14+
r = mid
15+
}
16+
}
17+
18+
return nums[l]
19+
}

‎src/0153.Find-Minimum-in-Rotated-Sorted-Array/Solution_test.go

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
func TestSolution(t *testing.T) {
10+
// 测试用例
11+
cases := []struct {
12+
name string
13+
inputs []int
14+
expect int
15+
}{
16+
{"TestCase", []int{3, 4, 5, 1, 2}, 1},
17+
{"TestCase", []int{4, 5, 6, 7, 0, 1, 2}, 0},
18+
}
19+
20+
// 开始测试
21+
for i, c := range cases {
22+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
23+
got := findMin(c.inputs)
24+
if !reflect.DeepEqual(got, c.expect) {
25+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26+
c.expect, got, c.inputs)
27+
}
28+
})
29+
}
30+
}
31+
32+
// 压力测试
33+
func BenchmarkSolution(b *testing.B) {
34+
35+
}
36+
37+
// 使用案列
38+
func ExampleSolution() {
39+
40+
}

0 commit comments

Comments
 (0)
0