剑指Offer 11——旋转数组的最小数字 (简单)

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [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

方法一:完全遍历数组找最小值

虽然可以解出来,但不是最好的方法

方法二:寻找断层

有序数组旋转会有两种情况: 一:完全有序 二:部分有序

思路:我们先把数组的第一个数作为最小数,遍历数组,如果出现前一个数大于后一个数,那么后一个数就是最小数。 极端情况下时间复杂度是O(n);平均时间复杂度O(logn);

 public int minArray(int[] numbers) {
       int min = numbers[0];
       for(int i=0;i<numbers.length-1;i++){
          if(numbers[i]>numbers[i+1]){
             min = numbers[i+1];
             break;
          }
       }
       return min;
    }

执行用时: 0 ms , 在所有 Java 提交中击败了 100.00% 的用户

内存消耗: 38.1 MB , 在所有 Java 提交中击败了 90.27% 的用户的用户的用户的用户的用户

方法三:二分法(力扣获得较多认可的参考方法)

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/

end

评论