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 次旋转

解题思路

1.题目要求我们返回旋转数组的最小元素，我们可以使用二分查找找到旋转排序数组中的最小元素。

2.首先初始化两个指针`left`和`right`，它们分别表示数组的起始和结束索引。在while循环内部，它检查`left`索引处的元素是否小于`right`索引处的元素。如果是，则意味着数组已经按升序排序，最小元素位于`left`索引处。因此，它返回`left`索引处的元素。如果数组未排序，则计算`mid`索引为`left`和`right`的平均值。

3.然后，它将`mid`索引处的元素与`left`索引处的元素进行比较。如果`mid`索引处的元素大于`left`索引处的元素，则意味着最小元素位于数组的右半部分。因此，它将`left`指针更新为`mid + 1`。如果`mid`索引处的元素小于`left`索引处的元素，则意味着最小元素位于数组的左半部分。因此，它将`right`指针更新为`mid`。如果`mid`索引处的元素等于`left`索引处的元素，则意味着数组中存在重复元素。在这种情况下，它将`left`指针增加1。

4.循环继续，直到`left`指针小于`right`指针为止。此时，`left`指针将指向数组中的最小元素，并返回`left`索引处的元素。如果循环退出时仍未找到最小元素，则意味着数组已经按升序排序，最小元素位于`left`索引处。因此，它返回`left`索引处的元素。

代码实现

class Solution {public int minArray(int[] numbers) {int left = 0;int right = numbers.length - 1;while(left < right){if(numbers[left] < numbers[right]){return numbers[left];}int mid = (left + right) / 2;if(numbers[mid] > numbers[left]){left = mid + 1;}else if(numbers[mid] < numbers[left]){right = mid;}else{left ++;}}return numbers[left];}}

测试结果