《剑指Offer》中取旋转数组最小数的学习

coding 旋转数组

见书66页。

O(logN)的算法核心观点在于把旋转数组看成两个递增子数组，运用二分查找算法实现。先考虑没有重复数字的情况，再考虑有重复的情况。

无重复数的代码[JAVA版]

public class RolateArray {
  public static int getMinNum(int[] numbs) throws Exception{
      if(numbs == null || numbs.length == 0) throw new Exception("Invaid array!");
      int start = 0;
      int end = numbs.length - 1;
      int resultIndex = start; //　返回结果的下标默认为start，处理旋转度为0的情况
      while(numbs[start] >= numbs[end]) { //如果不满足这个条件，则原数组的旋转度为0
        　if(end - start == 1) { //　start 一定在左边子序列中，end一定在右子序列中
        　     resultIndex = end;
        　     break;
        　}
        　int mid = (start + end) / 2;
        　if(numbs[mid] >= numbs[start]) //在左子序列
        　    start = mid;
        　else if(numbs[mid] <= numbs[end]) // 在右子序列
        　   　end = mid;
      }
      return numbs[resultIndex];  
  }
  public static void main(String[] args){
       int[] a1 = {3, 4, 5, 1, 2, 3}; // 可以求出来
       int[] a2 = {3, 3, 3, 1, 2, 3}; //　可以得到正确答案
       int[] a3 = {3, 4, 5, 1, 1, 2}; 
       try{
           System.out.println(getMinNum(a1));
           System.out.println(getMinNum(a2));
           System.out.println(getMinNum(a3));
       }catch(Exception e){
       　 　System.out.println(e);
      }
  }
}

这个代码的问题在于有时候会因为重复数字而分错了组。当mid/start/end对应的值都相同的时候，这时候无法判断该往哪边移动。此时只能遍历了。

有重复版的代码

public class RolateArray{
    public static int getMinNum(int[] numbs) throws Exception {
        if(numbs == null || numbs.length == 0) throw new Exception("Invalid array!");
        int start = 0;
        int end = numbs.length - 1;
        int resultIndex = start;
        while(numbs[start] >= numbs[end]) {
            if(end - start == 1) {
                resultIndex = end;
                break;
            }
            int mid ＝ (start + end) / 2;
            if(numbs[start] == numbs[end] && numbs[start] == numbs[mid]){
                  int tmp = numbs[start];
                  // 循环找出最小值
                  for(int i = start + 1; i <= end; i++){
                      if(numbs[i] < tmp)
                         tmp = numbs[i];
                  }
                  return tmp;
            }
            else if(numbs[start] <= numbs[mid])
                //在左子序列中
                start = mid;
            else if(numbs[end] >= numbs[mid])
                //在右子序列中
                end = mid
        }
        return numbs[resultIndex];
    }
}