【剑指offer】-旋转数组的最小数字-06/67

一 题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

二 题目分析

  1. 该数组原来是一个单调递增的数组,将前n个数字旋转到后面,输出最小的数字,假如数组大小为0的话,则返回0。
  2. 直接遍历循环输出最小的,这样的方法是最暴力的(不提倡)
  3. 借鉴二分法的思维方式
    1
    2
    3
    4
    5
    6
    数组: 3 4 5     1 2 3
    ---1--- ---2---
    1. 原数组旋转后,必然是两个有序的递增序列
    2. 假如当前中间的元素小于最右面的元素,则证明现在处于2位置 left = mid + 1
    3. 假如当前中间的元素大于最右面的元素,则证明现在处于1位置 right = mid
    4. 假如当前中间的元素等于最右面的元素,则证明元素中出现了重复的,这时候需要挨个判断,直接right--

三 代码(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int[] array) {
int len = array.length;
if (len == 0) {
return 0;
} else {
int left = 0;
int right = len - 1;
while (left < right) {
int mid = (left + right) / 2;
if (array[mid] < array[right]) {
right = mid;
} else if (array[mid] > array[right]) {
left = mid + 1;
}else {
right--;
}
}
return array[left];
}
}
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信