(LeetCode系列)寻找旋转排序数组中的值

yirufeng
算法二分

发布于：Dec 8, 2020
次浏览

前言

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

为何每次选取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. 有重复值s

旋转排序数组中找目标值

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

}

参考

相关文章
(LeetCode系列)矩阵中的搜索套路总结套路总结 注意：方法一二代码较为简单，这里就不再赘述了 方法三上图中的方法三，我们以LeetCode 240为...Golang中刷题关于切片的一些坑问题1问题描述：递归的过程中，传递了一个切片作为参数，每次我们都需要对切片切取首元素，之后递归回来的时候发现切片中的元素还...go中的heap实现大根堆与小根堆小根堆 几个注意点： 我们使用Less比较的时候决定了大根堆或小根堆 push以及pop需要传入指针，因为涉及到改动。...不基于比较的排序找到数组排序后的最大差值题目描述给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序 注意不...

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://www.sivan.tech/2020/12/08/%E5%AF%BB%E6%89%BE%E6%97%8B%E8%BD%AC%E6%8E%92%E5%BA%8F%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E5%80%BC/

更新于：Feb 7, 2021

二分

算法

评论