旋转数组最小值II

旋转数组最小值II

题目

一个有序的数组,在从某一个位置开始,旋转到数组的另一端

举例:

0 1 2 3 4 5 6 -> 4 5 6 0 1 2 3

在这个变换之后的数组中,找到最小值。

注意:

  • 有可能不旋转的哦。
  • 数组元素有重复

题目来自Leetcode: Find Minimum in Rotated Sorted Array II

分析

之前分析过没有重复的情况,最主要的有两点:

  1. 考虑完全思路
  2. 找好切入点

其实这两点是相关的,一个好的切入点,有利于覆盖完全的思路。这里的切入点可能有,用left,right,mid表示数组的左右中索引:

  1. left和mid的数组值关系
  2. left和right的数组值关系

right和mid是一样的,那个入手好呢?见下图

手绘,忍着看

left和right的关系少,而且简单。我们不妨从这个开始判断。

其实Leetcode上有问到,有什么变化?其实变化就在于num[left]==num[mid]==num[right]的时候,需要两边都要考虑,不能只考虑一边。

对照着上面的图,大家仔细体会。和图一样粗糙的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
public int min(int a, int b) {
if (a < b) return a;
return b;
}
public int findMin(int[] num, int left, int right) {
while(left < right) {
if (num[left] < num[right]) {
return num[left];
}
int mid = (left + right) / 2;
if (num[left] < num[mid]) {
left = mid + 1;
} else if (num[left] > num[mid]) {
right = mid;
} else {
return min(findMin(num, left, mid), findMin(num, mid + 1, right));
}
}
return num[left];
}
public int findMin(int[] num) {
return findMin(num, 0, num.length - 1);
}
}