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

难度简单236收藏分享切换为英文接收动态反馈
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为1。
示例 1:
输入:[3,4,5,1,2]
输出:1

示例 2:
输入:[2,2,2,0,1]
输出:0

注意:本题与主站 154 题相同:https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

方案1

解题思路

遍历一边,找一个最小的,返回即可。

解题代码

  1. public int minArray(int[] numbers) {
  2. int min = Integer.MAX_VALUE;
  3. for (int number : numbers) {
  4. min = Math.min(min,number);
  5. }
  6. return min;
  7. }

方案2

解题思路

例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为1。

给定的数组是有序的,所以是有规律的,可以使用二分查找的办法,可以增加效率。

时间复杂度:O(longn),空间复杂度:O(1)

算法流程:

  • 1、初始化left和right
  • 2、每次计算中间下标 mid = (right + left ) / 2;注:这里除法必需为整数,不能出现小数,因为是求的下标。
  • 3、当numbers[mid] < numbsers[right]时,说明最小值在[left,mid]区间,则令right=mid,继续下一轮查找;
  • 4、当numbers[mid] > numbers[left]时,说明最小的值在[mid,right]区间,则令left=mid+1,继续下一轮查找;
  • 5、当numbers[mid] == numbers[right]时,无法判断最小值在哪个区间之中,此时让right—,缩小区间范围,继续下一轮查找;
    • 这里为什么使用right—?而不是left++呢?
      • 因为数组时升序的,所以最小值一定靠近左侧,而不是右侧;
      • 比如:当存在[1,2,2,2,2]这种情况时,left=0,right=4,mid=2,数值满足numbers[mid] == numbers[right]这个条件,此时就无法判断在左⬅️区间,还是右➡️区间。如果left++的话,就会错过小的数字,永远找不到最小的数,所以此时应该right—。
  • 6、最终,left就是最小值的坐标,返回numbers[left]即可。

解题代码

  1. public int minArray(int[] numbers) {
  2. int left = 0;
  3. int right = numbers.length - 1;
  4. while ( left < right ){
  5. int mid = (left + right) / 2;
  6. if( numbers[mid] < numbers[right] ){
  7. right = mid;
  8. }else if(numbers[mid] > numbers[right]){
  9. left = mid + 1;
  10. }else {
  11. right--;
  12. }
  13. }
  14. return numbers[left];
  15. }