题解 | #旋转数组的最小数字#
旋转数组的最小数字
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
前后指针法
分析：旋转数组的特点是，左右两部分都为单调递增的数据 我们遍历数组 第一次遇到递减的情况 只需对比第一个数据与当前数据的大小 返回较小的一个即可
func minNumberInRotateArray(rotateArray []int) int {
// write code here
var res int
if len(rotateArray) == 1 {
return rotateArray[0]
}
pre := 0
tail := 1
for pre, tail = 0, 1; tail < len(rotateArray)-1; pre, tail = pre+1, tail+1 {
if rotateArray[pre] > rotateArray[tail] {
// 开始单调递减
break
}
}
res = min(rotateArray[0], rotateArray[tail])
return res
}
func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
二分法
面试官希望看到的方法
由于旋转数组第一次二分时 两个子数组各自都是单调递增的 可以使用二分法
func minNumberInRotateArray(rotateArray []int) int {
// write code here
size := len(rotateArray)
if size == 1 {
return rotateArray[0]
}
return min(minNumberInRotateArray(rotateArray[0:(size/2)]),minNumberInRotateArray(rotateArray[(size/2):size]))
}
func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
