旋转数组的最小数字

发表于

描述
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值0≤val≤10000
要求：空间复杂度O(1)，时间复杂度O(logn)

示例1

1
2
输入:  [3,4,5,1,2]
返回:  1

示例2

1
2
输入:  [3,100,200,3]
返回:  3

题解

  • 数组可以分为两个有序的子数组。其中，左排序的数组的值大于右排序数组中的值
  • 声明left,right 分别指向数组的左右两端
  • mid = (left+right) / 2 为二分的中间位置
  • mid，left,right分为三种情况
    • rotateArray[mid] > rotateArray[right]时， 那么 最小值一定在 [mid+1,right]区间中
    • rotateArray[mid] < rotateArray[right]时，那么最小值一定在[left,mid]区间内
    • rotateArray[mid] = rotateArray[right]时，无法判断最小值在哪个区间，所以此时只能缩小right的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

/**
 * 
 * @param rotateArray int整型一维数组 
 * @return int整型
*/
func minNumberInRotateArray( rotateArray []int ) int {
    // write code here
    left, right := 0, len(rotateArray) - 1
    for left < right {
        mid :=  left + (right - left)>>1
        if rotateArray[mid] < rotateArray[right] {
            right = mid
        } else if rotateArray[mid] > rotateArray[right] {
            left = mid + 1
        } else {
            right -= 1
        }
    }

    return rotateArray[left]
}