前言

在旋转数据中搜索值包括两个系列的题型:搜索旋转点(也就是最小值)以及搜索我们给定的目标值。关于旋转排序数组的定义这里就不再赘述

为何每次选取mid位置对应的元素与right位置对应的元素比较

3TrZGv

旋转排序数组中找旋转点

aNLEXp

寻找旋转点其实也就是寻找旋转排序数组中的最小值

这个问题下又包含两个题目:一个是给定的旋转排序数组没有重复值,另外一个是给定的旋转排序数组中有重复值

选择target

因为题目中没有给出明显的target,对于这类型题目,一般我们都是选取端点。

这里假设选取左端点,如果nums[mid] > nums[l],并不能说明最小值就在mid左边,因为可能数组发生了旋转,最小值会在mid右边,因而使用nums[l]作为target无法确定最小值在哪一侧。

3TrZGv

因而这里我们选择右侧即nums[r]

没有重复值

思路

每次我们都在有效的搜索区间[l, r]中找到该区间上的中点mid,此时有以下几种情形:

  1. nums[mid] > nums[r] 说明数组在[l, mid]上是递增的,因此旋转点一定在mid右侧,l = mid + 1
  2. nums[mid] < nums[r] 说明数组在[mid, r]上是递增的,因此旋转点一定在mid左侧(包含mid),r = mid
  3. nums[mid] == nums[r] 因为数组中不存在重复值,所以当出现这种情况时,一定有l == mid == r 此时一定指向最小值,直接返回即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findMin(nums []int) int {
l, r := 0, len(nums)-1
for l <= r {
if nums[l] < nums[r] {
return nums[l]
}

mid := l + (r-l)>>1
if nums[mid] > nums[r] {
l = mid + 1
} else if nums[mid] < nums[r] {
r = mid
} else if nums[mid] == nums[r] {
return nums[mid]
}
}

//随便返回一个即可,不会走到这里
//因为最小值一定存在
return -1
}

有重复值

思路

每次我们都在有效的搜索区间[l, r]中找到该区间上的中点mid,此时有以下几种情形:

  1. nums[mid] > nums[r] 说明数组在[l, mid]上是递增的,因此旋转点一定在mid右侧,l = mid + 1
  2. nums[mid] < nums[r] 说明数组在[mid, r]上是递增的,因此旋转点一定在mid左侧(包含mid),r = mid
  3. nums[mid] == nums[r] 此时最小值可能在左侧也可能在右侧,例如[1, 1, 1, 0, 1]最小值在右侧,[1, 0, 1, 1, 1]最小值在左侧,因而无法确定。所以只能一步一步不断缩减区间,让r = r - 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func findMin(nums []int) int {
if len(nums) == 0 {
return 0
}

l, r := 0, len(nums)-1
for l <= r {
if nums[l] < nums[r] {
return nums[l]
}
mid := l + (r-l)>>1
if nums[mid] > nums[r] {
l = mid + 1
} else if nums[mid] < nums[r] {
r = mid
} else if nums[mid] == nums[r] {
r = r - 1
}
}

//最后结束时一定有l = r + 1,所以因为r向左移动了一步就直接返回l
return nums[l]
}s

参考

  1. 没有重复值
  2. 有重复值

旋转排序数组中找目标值

VcG9Gr

数组中元素没有重复

IMG_6A121E8AEE6E-1

代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

/** ✅
* @Author: yirufeng
* @Date: 2020/12/3 7:52 下午
* @Desc:
执行用时:4 ms, 在所有 Go 提交中击败了78.30%的用户
内存消耗:2.5 MB, 在所有 Go 提交中击败了96.57%的用户
**/
func search(nums []int, target int) int {
if len(nums) == 0 {
return 0
}

l, r := 0, len(nums)-1
for l <= r {
mid := l + (r-l)>>1
if nums[mid] == target {
return mid
}

if nums[mid] < nums[r] { //说明[mid, r]上是递增的

if target < nums[mid] {
r = mid - 1
} else if target > nums[mid] {
if target <= nums[r] {
l = mid + 1
} else if target > nums[r] {
r = mid - 1
}
}

} else if nums[mid] > nums[r] { //说明此时[l, mid]上是递增的
if target > nums[mid] {
l = mid + 1
} else if target < nums[mid] {
if target >= nums[l] {
r = mid - 1
} else if target < nums[l] {
l = mid + 1
}
}

} else if nums[mid] == nums[r] { //说明此时l,r以及mid指向同一个元素
//此时判断该元素是否为目标值,
//因为在前面我们执行了nums[mid]==target所以这里肯定不是等于目标值
//所以返回-1
return -1
}
}

//一定不会执行到这里
return -1
}

//对上面的代码进行优化
//执行用时:4 ms, 在所有 Go 提交中击败了78.30%的用户
//内存消耗:2.5 MB, 在所有 Go 提交中击败了96.57%的用户
func search(nums []int, target int) int {
if len(nums) == 0 {
return 0
}

l, r := 0, len(nums)-1
for l <= r {
mid := l + (r-l)>>1
if nums[mid] == target {
return mid
}

if nums[mid] < nums[r] { //说明[mid, r]上是递增的

/*if target < nums[mid] {
r = mid - 1
} else if target > nums[mid] {
if target <= nums[r] {
l = mid + 1
} else if target > nums[r] {
r = mid - 1
}
}*/

//上面注释代码改成这样
if target > nums[mid] && target <= nums[r] {
l = mid + 1
} else {
r = mid - 1
}
} else if nums[mid] > nums[r] { //说明此时[l, mid]上是递增的
/*if target > nums[mid] {
l = mid + 1
} else if target < nums[mid] {
if target >= nums[l] {
r = mid - 1
} else if target < nums[l] {
l = mid + 1
}
}*/

//上面注释代码改成这样
if target < nums[mid] && target >= nums[l] {
r = mid - 1
} else {
l = mid + 1
}

} else if nums[mid] == nums[r] { //说明此时l,r以及mid指向同一个元素
//此时判断该元素是否为目标值,
//因为在前面我们执行了nums[mid]==target所以这里肯定不是等于目标值
//所以返回-1
return -1
}
}

//一定不会执行到这里
return -1
}

数组中元素有重复

IMG_2D812A217949-1

代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

//不同于33题就在于nums[mid]==nums[r]的情况,此时因为数组中有重复元素,不同于33题,并不能判断l, mid, r都指向同一个元素,所以只能不断缩减区间
//执行用时:4 ms, 在所有 Go 提交中击败了90.74%的用户
//内存消耗:3.2 MB, 在所有 Go 提交中击败了95.60%的用户
func search(nums []int, target int) bool {
if len(nums) == 0 {
return false
}

l, r := 0, len(nums)-1
for l <= r {
mid := l + (r-l)>>1
if target == nums[mid] {
return true
}

if nums[mid] > nums[r] { //说明此时[l, mid]是单调递增的
if target > nums[mid] {
l = mid + 1
} else if target < nums[mid] {
if target >= nums[l] {
r = mid - 1
} else if target < nums[l] {
l = mid + 1
}
}
} else if nums[mid] < nums[r] {
if target < nums[mid] {
r = mid - 1
} else if target > nums[mid] {
if target <= nums[r] {
l = mid + 1
} else if target > nums[r] {
r = mid - 1
}
}

} else if nums[mid] == nums[r] { //关键点:不同于33题的
//因为数组中有重复元素,我们不能确定l, mid, r是指向同一个元素的
//因此让r不断缩减
r--
}
}

//最后一定不会执行到这里
return false

}

//对上面的代码进行优化
//执行用时:4 ms, 在所有 Go 提交中击败了90.74%的用户
//内存消耗:3.2 MB, 在所有 Go 提交中击败了95.60%的用户
func search(nums []int, target int) bool {
if len(nums) == 0 {
return false
}

l, r := 0, len(nums)-1
for l <= r {
mid := l + (r-l)>>1
if target == nums[mid] {
return true
}

if nums[mid] > nums[r] { //说明此时[l, mid]是单调递增的
//if target > nums[mid] {
// l = mid + 1
//} else if target < nums[mid] {
// if target >= nums[l] {
// r = mid - 1
// } else if target < nums[l] {
// l = mid + 1
// }
//}
if target < nums[mid] && target >= nums[l] {
r = mid - 1
} else {
l = mid + 1
}
} else if nums[mid] < nums[r] {
//if target < nums[mid] {
// r = mid - 1
//} else if target > nums[mid] {
// if target <= nums[r] {
// l = mid + 1
// } else if target > nums[r] {
// r = mid - 1
// }
//}

if target > nums[mid] && target <= nums[r] {
l = mid + 1
} else {
r = mid - 1
}

} else if nums[mid] == nums[r] { //关键点:不同于33题的
//因为数组中有重复元素,我们不能确定l, mid, r是指向同一个元素的
//因此让r不断缩减
r--
}
}

//最后一定不会执行到这里
return false

}

参考

评论