数据结构与算法

旋转数组的最小数字

略

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

  用顺序查找就可以实现，但面对大量的数据时，可以用算法来优化查找。

分析

常规情况

  对于一个旋转数组，第一个元素是比最后一个元素大的（大多数情况下，特殊情况下文中再说）；那么对于这样的数组要实现查找，自然想到了二分查找，但是二分之后，如何选择最小值在哪个区域呢？可以举个例子，例如：有旋转数组array，它的元素是{5,6,7,8,9,1,2,3,4}，它的头是array[0]=5，它的尾是array[8]=4，中间是array[4]=9，然后旋转数组的头一定是大于尾部的（排除特殊情况），然而中间的9大于5（比头还大），所以最小值在中间的右边，把头的指针移动到中间，在{9,1,2,3,4}中去找最小值，依次类推，头为9，尾为4，中为2，中小于尾（比尾还小），所以最小值在中间的左边，把尾的指针移动到中间，最后{9,1,2}中找最小值，头为9，尾为2，中为1，1小于2（比尾还小），尾部指针移动到中间，{9,1}中找最小，由于他们相距为1，则循环结束，输出尾指针，就是最小值了。

  所以程序应该这么写：用头、尾指针来划定范围，中指针来判断如何移动头尾指针，如果中大于或等于头，则头指针移到中，如果中小于或等于尾，则尾指针移动到中，概括来就是：头大于尾，中间取数，与头比大，与尾比小，大头移头，小尾移尾，距离为1，尾部最小。

特殊情况

  有时候会出现，旋转了0个元素的情况：就是没有旋转如{1,2,3,4,5,6}，再用二分就不可以了，因为上文一直是在由尾元素来得到最小值，然而这次最小元素在第一个，不能是尾元素，所以说上文的程序是有前提条件的，那就是头比尾大，当头比尾小的时候就说明没有旋转，直接输出第一个元素就好了。

  还有一种情况：那就是当出现头，尾，中三个元素相等的时候，例如{1,0,1,1,1}或者{1,1,1,0,1}，说明上述程序并不完整，这时候就需要判断，当三元素相等时，就采用其他的查找方式，例如顺序查找。

代码实现

代码如下：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
      
    	if(array == null || array.length == 0){
            return 0;
        }
      
        int head = 0;
        int foot = array.length - 1;
        int mid = head;//这里为了防止0旋转数组，中指针用头初始化
      
        while(array[head] >= array[foot]){//当头大于尾才进入循环
          
            if(foot-head==1){//距离为1时，把尾赋给中，跳出循环
                mid = foot;
                break;
            }
            
            mid = (head + foot)/2;
          
            if(array[head]==array[foot] 
               && array[head]==array[mid]){//三元素相等，用顺序查找
                return MinInOrder(array,head,foot);
            }
          
            if(array[mid]>=array[head]){//与头比大
                head = mid;
            }
          
            if(array[mid]<=array[foot]){//与尾比小
                foot = mid;
            }
        }
        return array[mid];//（前面有把尾赋给中）把中输出
    }
    
    public int MinInOrder(int [] array,int head, int foot){//顺序查找
        int result = array[head];
       	for(int i = head + 1;i<=foot;i++){
            if(result > array[i])
                result = array[i];
        }
        return result;
    }
}

总结

  1. 虽然顺序查找可以做到，但是还要思考是否有更好的方法，如二分法。
  2. 要考虑到旋转数组的特例，如{1,2,3,4,5,6}和{1,1,1,0,1}。
  3. 后面的学习中要要求把二分查找学到信手拈来的程度。