leetcode剑指 Offer 11. 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

示例 1：

输入：numbers = [3,4,5,1,2] 输出：1 示例 2：

输入：numbers = [2,2,2,0,1] 输出：0

提示：

n == numbers.length 1 <= n <= 5000 -5000 <= numbers[i] <= 5000 numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

旋转数组:
有序数组经过旋转后得到的
将最后的几个元素拿到前面来了\

法1

暴力迭代:
找最小的数比较容易但低效的方法 遍历数组找到最小的数

• 时间复杂度(O(n))
• 空间复杂度(O(1))

法2,

暴力迭代优化
增加判断条件,减少判断次数:\

要知道,在反转之前,数组是一个递增的数组,那旋转之后也是一个区域性递增的数组,在临界点处会出现不同,我们只需要迭代到临界点就可以了不用迭代完这个数组.

• 时间复杂度(O(n))
• 空间复杂度(O(1))

法3

二分法
二分法的条件:有序
题目是满足二分法的使用条件 的,它是临界有序类型,也是有序的,而我们要找到就是就是对数据对半索引,因为是临界有序类型,且临界点左边的数大于右边的数,判断一半的值在左边还是右边,如果大于最后的值就是在右边,小于最后的值就是在左边,,,
这只是普通的情况

• 特殊情况:
  但出现重复数据在数组中时 比如n=[5,5,5,5,5,2,5,5]或者n=[5,5,2,5,5,5,5,5] 我们无法通过判断中间数与最后一个数的关系去判断数据在左侧或者是右侧.所以当我们遇到这种情况时,我们不能根据判断去丢掉任何一侧,所以我们需要缩小数组长度.l--从而找到最小的数
• 时间复杂度(O(log n))
• 空间复杂度(O(1))

执行结果

法1

func minArray(numbers []int) int {
 n:=numbers[0]
for i:=0;i<len(numbers);i++ {
 if n>numbers[i] {
  n=numbers[i]
 }
}
return n
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 4 ms , 在所有 Go 提交中击败了 79.49% 的用户 内存消耗： 2.9 MB , 在所有 Go 提交中击败了 97.55% 的用户 通过测试用例： 192 / 192

法2

func minArray(numbers []int) int {
 if numbers[0]<numbers[len(numbers)-1] {//如果是全有序,就后返回第一个
  return numbers[0]
 }
 for i := 1; i < len(numbers); i++ {
  if numbers[i] < numbers[i-1] && numbers[i] < numbers[i+1] {//访问到临界点为止
   return numbers[i]
  }
 }
 return numbers[len(numbers)-1]//如果没有就是最后一个最小
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.9 MB , 在所有 Go 提交中击败了 97.55% 的用户 通过测试用例： 192 / 192

法3

func minArray(numbers []int) int {
 l := len(numbers)
 for i, j := l/2, l/2; j > 0; {
  if i <= 0 {
   return numbers[0]
  }
  if numbers[i] < numbers[i-1] {
   return numbers[i]
  }
  if j/2 == 0 {
   j = 1
  } else {
   j /= 2
  }
  if numbers[0] == numbers[l-1] && numbers[i] == numbers[0]&&i!=0&&i!=l-1 {
   l = l - 1
   continue
  }
  if numbers[i] > numbers[l-1] { //说明在旋转部分
   i = i + j
  } else {
   i = i - j
  }
 }
 return numbers[l-1]
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 4 ms , 在所有 Go 提交中击败了 79.49% 的用户 内存消耗： 2.9 MB , 在所有 Go 提交中击败了 97.55% 的用户 通过测试用例： 192 / 192

• 结构优化

func minArray(numbers []int) int {
 low := 0
 high := len(numbers) - 1
 for low < high {
  pivot := low + (high - low) / 2
        if numbers[pivot] < numbers[high] {
            high = pivot
        } else if numbers[pivot] > numbers[high] {
            low = pivot + 1
        } else {
            high--
        }
 }
 return numbers[low]
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 4 ms , 在所有 Go 提交中击败了 79.49% 的用户 内存消耗： 2.9 MB , 在所有 Go 提交中击败了 77.61% 的用户 通过测试用例： 192 / 192