旋转数组的最小数字(Golang)《剑指offer》


题目描述:

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如:数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。

注意:本题中应充分考虑特殊情况
func finMinNum(nums []int) int {
	if len(nums) == 0 {
		return -1
	}
	start := 0
	end := len(nums) - 1
	mid := start // 如果第一个数字小于最后一个数字,那就说明该数组是有序的,直接返回第一个数字
	for nums[start] >= nums[end] {
		if end-start == 1 {
			mid = end
			break
		}
		mid = (start + end) / 2
		// 如果第一个、最后一个和中间的数字都相等,那么只能按照顺序查找
		if nums[start] == nums[mid] && nums[mid] == nums[end] {
			return finMinInOrder(nums)
		}

		if nums[mid] >= nums[start] {
			start = mid
		} else if nums[mid] <= nums[end] {
			end = mid
		}
	}
	return nums[mid]
}
完整代码请参考:https://github.com/echaser/algorithm

文章作者: Jack Li
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Jack Li !
评论
  目录