16. leetCode--剑指Offer11旋转数组的最小数字

剑指Offer11旋转数组的最小数字

题目连接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/题目难度： 简单

1. 问题描述

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

2. 代码实现

2.1 方法一 暴力解法

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

2.2 方法二 二分法

推荐使用，想法很不错。

public class Solution { public int minArray(int[] numbers) { int left = 0; int right = numbers.length - 1; // [3,4,5,1,2] while(left < right){ // 0 + (4 - 0)/2 int mid = left + (right -left)/2; // 最小值在 mid -- right 之间 if (numbers[mid] > numbers[right]){ left = mid + 1; // 最小值在 left -- mid 之间 }else if (numbers[mid] < numbers[right]){ right = mid; }else{ right--; } } return numbers[left]; } }

3. 测试结果

方法一：

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户内存消耗：39.6 MB, 在所有 Java 提交中击败了50.90%的用户

方法二：

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户内存消耗：39.5 MB, 在所有 Java 提交中击败了56.05%的用户

##　☆