1. <dd id="qfst8"><pre id="qfst8"></pre></dd>
      <nav id="qfst8"><sub id="qfst8"><noframes id="qfst8"></noframes></sub></nav>
      <tbody id="qfst8"><pre id="qfst8"></pre></tbody>

      <dd id="qfst8"><track id="qfst8"></track></dd>
        1. 首頁 > 試題廣場 > 旋轉數組的最小數字
          [編程題]旋轉數組的最小數字
          把一個數組最開始的若干個元素搬到數組的末尾,我們稱之為數組的旋轉。
          輸入一個非遞減排序的數組的一個旋轉,輸出旋轉數組的最小元素。
          例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉,該數組的最小值為1。
          NOTE:給出的所有元素都大于0,若數組大小為0,請返回0。
          推薦
          思路

          劍指Offer中

             查看全部
          編輯于 2015-08-18 23:34:39 回復(120)
          采用二分法解答這個問題,
          mid = low + (high - low)/2
          需要考慮三種情況:
          (1)array[mid] > array[high]:
          出現這種情況的array類似[3,4,5,6,0,1,2],此時最小數字一定在mid的右邊。
          low = mid + 1
          (2)array[mid] == array[high]:
          出現這種情況的array類似 [1,0,1,1,1] 或者[1,1,1,0,1],此時最小數字不好判斷在mid左邊
          還是右邊,這時只好一個一個試 ,
          high = high - 1
          (3)array[mid] < array[high]:
          出現這種情況的array類似[2,2,3,4,5,6,6],此時最小數字一定就是array[mid]或者在mid的左
          邊。因為右邊必然都是遞增的。
          high = mid
          注意這里有個坑:如果待查詢的范圍最后只剩兩個數,那么mid 一定會指向下標靠前的數字
          比如 array = [4,6]
          array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
          如果high = mid - 1,就會產生錯誤, 因此high = mid
          但情形(1)中low = mid + 1就不會錯誤
          public class Solution {
              public int minNumberInRotateArray(int [] array) {
                  int low = 0 ; int high = array.length - 1;    
                  while(low < high){
                      int mid = low + (high - low) / 2;         
                      if(array[mid] > array[high]){
                          low = mid + 1;
                      }else if(array[mid] == array[high]){
                          high = high - 1;
                      }else{
                          high = mid;
                      }    
                  } 
                  return array[low];
              }
          }
          編輯于 2017-08-01 13:06:40 回復(172)
          //C++ 二分法
          class Solution {
          public:
          ? ? int minNumberInRotateArray(vector<int> rotateArray) {
          ? ? ? ? if (rotateArray.empty()) return 0;
          ? ? ? ? int left = 0, right = rotateArray.size() - 1;
          ? ? ? ? while (left < right) {
          ? ? ? ? ? ? //確認子數組是否是類似1,1,2,4,5,..,7的非遞減數組
          ? ? ? ? ? ? if (rotateArray[left] < rotateArray[right]) return rotateArray[left];
          ? ? ? ? ? ??
          ? ? ? ? ? ? int mid = left + (right - left) / 2;
          ? ? ? ? ? ? //如果左半數組為有序數組
          ? ? ? ? ? ? if (rotateArray[left] < rotateArray[mid])
          ? ? ? ? ? ? ? ? left = mid + 1;
          ? ? ? ? ? ? //如果右半數組為有序數組
          ? ? ? ? ? ? else if (rotateArray[mid] < rotateArray[right])
          ? ? ? ? ? ? ? ? right = mid;
          ? ? ? ? ? ? //否則,rotateArray[left] == rotateArray[mid] == rotateArray[right]
          ? ? ? ? ? ? else {
          ? ? ? ? ? ? ? ? ++left;
          ? ? ? ? ? ? }
          ? ? ? ? }
          ? ? ? ? return rotateArray[left];
          ? ? }
          };
          
          

          發表于 2018-05-17 10:48:25 回復(14)
          三種方法,
          1、最笨的一種:
          ? ? 遍歷整個數組,找出其中最小的數。這樣肯定拿不到offer
          2、稍微優化:
          ???public int minNumberInRotateArray(int[] array) {
          		if (array.length == 0)
          			return 0;
          		for (int i = 0; i < array.length - 1; i++) {
          			if (array[i] > array[i + 1])
          				return array[i + 1];
          		}
          		return array[0];
          	}?
          3、二分查找:
          public static int minNumberInRotateArray(int[] array) {
          		if (array.length == 0)
          			return 0;
          		int left = 0;
          		int right = array.length - 1;
          		int middle = -1;
          		while (array[left]>=array[right]) {
          			if(right-left==1){
          				middle = right;
          				break;
          			}
          			middle = left + (right - left) / 2;
          			if (array[middle] >= array[left]) {
          				left = middle;
          			}
          			if (array[middle] <= array[right]) {
          				right = middle;
          			}
          		}
          		return array[middle];
          	}

          發表于 2017-01-09 10:57:17 回復(39)
          Python方法大總結
          方法一:直接min函數,有點像開掛
          class Solution:
          ? ? def minNumberInRotateArray(self, rotateArray):
          ? ? ? ? # write code here
          ? ? ? ? if not rotateArray:
          ? ? ? ? ? ? return 0
          ? ? ? ? else:
          ? ? ? ? ? ? return min(rotateArray)
          方法二:先sort排序
          class Solution:
          ? ? def minNumberInRotateArray(self, rotateArray):
          ? ? ? ? # write code here
          ? ? ? ? if not rotateArray:
          ? ? ? ? ? ? return 0
          ? ? ? ? else:
          ? ? ? ? ? ? rotateArray.sort()
          ? ? ? ? ? ? return rotateArray[0]
          方法三:二分查找
          class Solution:
          ? ? def minNumberInRotateArray(self, rotateArray):
          ? ? ? ? # write code here
          ? ? ? ? length = len(rotateArray)
          ? ? ? ? if length == 0:
          ? ? ? ? ? ?return 0
          ? ? ? ? elif length == 1:
          ? ? ? ? ? ? return rotateArray[0]
          ? ? ? ? else:
          ? ? ? ? ? ? left = 0
          ? ? ? ? ? ? right = length - 1
          ? ? ? ? ? ? while left < right:
          ? ? ? ? ? ? ? ? mid = (left + right)/2
          ? ? ? ? ? ? ? ? if rotateArray[mid] < rotateArray[j]:
          ? ? ? ? ? ? ? ? ? ? right = mid
          ? ? ? ? ? ? ? ? else:
          ? ? ? ? ? ? ? ? ? ? left = mid+1
          ? ? ? ? ? ? return rotateArray[i]
          方法四:比較
          class Solution:
          ? ? def minNumberInRotateArray(self, rotateArray):
          ? ? ? ? # write code here
          ? ? ? ? length = len(rotateArray)
          ? ? ? ? if length == 0:
          ? ? ? ? ? ?return 0
          ? ? ? ? elif length == 1:
          ? ? ? ? ? ? return rotateArray[0]
          ? ? ? ? else:
          ? ? ? ? ? ? for i in range(length-1):
          ? ? ? ? ? ? ? ? if rotateArray[i] > rotateArray[i+1]:
          ? ? ? ? ? ? ? ? ? ? return rotateArray[i+1]
          ? ? ? ? ? ? return rotateArray[length-1]
          人生苦短,我用Python
          發表于 2016-08-27 14:51:27 回復(16)
          此題比較扯的。但題目還是不錯。
          比較扯的原因:
          1.當數組為空的時候,測試用例需要返回0,我返回-1,結果沒通過。
          2.明明題目說是遞增數列,測試用里面竟然有非遞減數列。

          正確做法需要分為:
          1.數組為空
          2.部分旋轉,例如由(1,2,3,4,5)旋轉為(3,4,5,1,2),此時只需要遍歷數組,找到當前數比前面的數小的數即可。
          3.完全旋轉,例如由(1,2,3,4,5)旋轉為(1,2,3,4,5),此時第一個數最小。
          class Solution {
          public:
          ????int minNumberInRotateArray(vector<int> rotateArray) {
          
          ????????//數組為空時
          ????????if(rotateArray.size() == 0)
          ????????????return -1;
          ????????//前部分數據旋轉
          ????????for(int i = 0; i < rotateArray.size() - 1; i++){
          ????????????if (rotateArray[i] > rotateArray[i + 1])
          ????????????????return rotateArray[i + 1];
          ????????}
          
          ????????//全部數據旋轉,相當于沒有旋轉,最小數即為第一個數
          ????????return rotateArray[0];
          ????}
          };
          

          發表于 2015-05-13 14:43:11 回復(33)
          XD頭像 XD
          /*把一個數組最開始的若干個元素搬到數組的末尾,我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉,輸出旋轉數組的最小元素。例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉,該數組的最小值為1。*/
          根據題意說明是一個遞增數組的旋轉,所以如題所示【3,4,5】,【1,2】還是局部遞增的,在這種的數組中查找,一般選擇二分的方法;基本模型有了,下面試著分析:
          1.先取出中間的數值,和最后一個比較5>2 說明mid之前的某些部分旋轉到了后面,所以下次尋找 low = mid+1 開始;
          2.取出的中間值要是小于high,說明mid-high之間都應為被旋轉的部分,所以最小應該在mid的前面,但是也有可能當前的mid 就是最小的值 所以下次需找的應該 從mid開始,也即high = mid 開始
          3.當*mid == *high的時候,說明數組中存在著相等的數值,可能是這樣的形式 【2,2,2,2,1,2】所以應該選擇的high 應該遞減1 作為下次尋找的上界。
          參考代碼如下:
            int minNumberInRotateArray(vector<int> rotateArray) {  
              size_t len = rotateArray.size();
              if(len == 0)
                  return 0;
              if(len == 1)
                  return rotateArray[0];
              vector<int>::iterator low = rotateArray.begin();
              vector<int>::iterator mid;
              vector<int>::iterator high = rotateArray.end()-1;
              while(low <= high)
              {
                  //防止迭代器失效
                  mid = low + (high - low)/2;
                  if(*mid >*high)
                  {
                      low = mid + 1;
                  }
                  else if(*mid < *high)
                  {
                      high = mid;
                  }
                  else
                  {
                      high = high-1;
                  }
                  if(low >= high)
                  {
                      break;
                  }
              }
                  return *low;
              }  

          發表于 2015-08-11 14:03:13 回復(5)
          public class Solution {
           /*
           * 傳進去旋轉數組,注意旋轉數組的特性:
           * 1.包含兩個有序序列
           * 2.最小數一定位于第二個序列的開頭
           * 3.前序列的值都>=后序列的值
           * 定義把一個數組最開始的若干個元素搬到數組的末尾,我們稱之為數組的旋轉。
           * ^_^這個旋轉思想是很經典的
           * 旋轉數組實例:
           * {123456}旋轉后{456123}
           */
           
           //用到了快速排序的快速定位范圍的思想,
           public int minNumberInRotateArray(int [] array) {
          
           if(array==null||array.length==0){  return 0;
           }
           int low=0;
           int up=array.length-1;
           int mid=low;
           
           // 當low和up兩個指針相鄰時候,就找到了最小值,也就是
           //右邊序列的第一個值
           
           while(array[low]>=array[up]){
           if(up-low==1){
           mid=up;
           break;
           }
           //如果low、up、mid下標所指的值恰巧相等
           //如:{0,1,1,1,1}的旋轉數組{1,1,1,0,1}
           if(array[low]==array[up]&&array[mid]==array[low])
           return MinInOrder(array);
           ? ?mid=(low+up)/2;
           //這種情況,array[mid]仍然在左邊序列中
           if(array[mid]>=array[low])
           low=mid;//注意,不能寫成low=mid+1;
           //要是這種情況,array[mid]仍然在右邊序列中
           else if(array[mid]<=array[up])
           up=mid;
           }
           
           return array[mid];
           ? ?
          ? ? }
           private int MinInOrder(int[] array) {
           // TODO Auto-generated method stub
           int min =array[0];
           for(int i=1;i<array.length;i++){
           if(array[i]<min){
           min=array[i];
           
           }
           }
           return min;
           }
           public static void main(String[] args) {
           
           }
          
          }
          
          

          編輯于 2015-04-11 17:55:45 回復(5)

          python solution:

          # -*- coding:utf-8 -*-
          class Solution:
              def minNumberInRotateArray(self, rotateArray):
                  # write code here
                  return min(rotateArray)
          
          發表于 2017-10-07 19:14:16 回復(18)
          # -*- coding:utf-8 -*-
          class Solution:
          ? ? def minNumberInRotateArray(self, rotateArray):
          ? ? ? ? # write code here
          ? ? ? ? for i in range(len(rotateArray)):
          ? ? ? ? ? ? if rotateArray[i+1] < rotateArray[i]:
          ? ? ? ? ? ? ? ? return rotateArray[i+1]
          ? ? ? ? return 0
          

          發表于 2018-03-20 16:05:21 回復(0)
          前方大坑!!
          rotateArray.size() == 0時候返回一個0
          這個設定極其不合理,無法區分是min=0還是出錯了


          遞歸代碼:
          class Solution {
              int findMin(vector<int> a, int first, int last) {
                  if (first >= last) return a[last];
                  int mid = (first + last) / 2;
                  if (a[first] == a[last] && a[mid] == a[first]) {
                      // linear search
                      int min = a[first];
                      for (int i = first + 1; i <= last; i++)
                          min = a[i]<min ? a[i] : min;
                      return min;
                  }
                  if (a[first] < a[last]) {
                      return a[first];
                  } else {
                      if (a[mid] >= a[first]) {
                          return findMin(a, mid + 1, last);
                      } else {
                          return findMin(a, first, mid);
                      }
                  }
              }
           
          public:
              int minNumberInRotateArray(vector<int> rotateArray) {
                  int n = rotateArray.size();
                  if (n == 0) return 0;
                  return findMin(rotateArray, 0, n - 1);
              }
          };
          
          
          循環代碼:
          class Solution {  
          public:
              int minNumberInRotateArray(vector<int> array) {
                  if (array.size() == 0) return 0;
                  int first = 0, last = array.size() - 1;
                  int mid = (first + last) / 2;
                  while (array[first] >= array[last]) {
                      if (last - first == 1) return array[last];
                      if (array[first] == array[mid] && array[mid] == array[last]) {
                          // linear search
                          int min = array[first];
                          for (int i = first + 1; i <= last; i++)
                              min = array[i]<min ? array[i] : min;
                          return min;
                      }
                       
                      if (array[first] <= array[mid]) first = mid;
                      else last = mid;
          
                      mid = (first + last) / 2;
                  }
                  return array[first];
              }
          };

          編輯于 2015-07-27 14:12:26 回復(6)
          package go.jacob.day0827.劍指offer系列;
          
          public class 旋轉數組的最小數字 {
          ? ? public int minNumberInRotateArray(int[] array) {
          ? ? ? ? if (array == null || array.length == 0) {
          ? ? ? ? ? ? return -1;
          ? ? ? ? }
          ? ? ? ? int len = array.length;
          
          ? ? ? ? int index1 = 0;
          ? ? ? ? int index2 = len - 1;
          ? ? ? ? int indexMid = index1;
          
          ? ? ? ? while (array[index1] >= array[index2]) {
          ? ? ? ? ? ? if (index1 == index2 - 1) {
          ? ? ? ? ? ? ? ? indexMid = index2;
          ? ? ? ? ? ? ? ? break;
          ? ? ? ? ? ? }
          ? ? ? ? ? ? indexMid = index1 + (index2 - index1) / 2;
          ? ? ? ? ? ? if (array[index1] <= array[indexMid]) {
          ? ? ? ? ? ? ? ? index1 = indexMid;
          ? ? ? ? ? ? } else if (array[indexMid] <= array[index2]) {
          ? ? ? ? ? ? ? ? index2 = indexMid;
          ? ? ? ? ? ? }
          ? ? ? ? }
          
          ? ? ? ? return array[indexMid];
          ? ? }
          
          
          }
          

          編輯于 2018-09-04 13:48:00 回復(1)
          其實就是二分查找,查找時分兩種情況:
          1、array[m] > array[r]:說明旋轉后最小值在右區間
          2、array[m] < array[r]:說明旋轉后最小值在左區間
          (l、r是待查找區間邊界,m是區間中間位置)

          class Solution {
          public:
          ? ? int minNumberInRotateArray(vector<int> array) {
          ? ? ? ? //二分查找
          ? ? ? ? if(array.size()==0){
          ? ? ? ? ? ? return 0;
          ? ? ? ? }
          ? ? ? ? int l=0, r=array.size()-1;
          ? ? ? ? while(l<r){
          ? ? ? ? ? ? int m = (l+r)>>1;
          ? ? ? ? ? ? if(array[m] > array[r]){
          ? ? ? ? ? ? ? ? l = m+1;
          ? ? ? ? ? ? }else{
          ? ? ? ? ? ? ? ? r = m;
          ? ? ? ? ? ? }
          ? ? ? ? }
          ? ? ? ? return array[l];
          ? ? }
          };
          發表于 2018-02-01 20:27:37 回復(4)
          我這個代碼感覺挺簡單的,測試通過。求大家挑挑毛病
          class Solution {
          public:
          ????int minNumberInRotateArray(vector<int> rotateArray) {
          ????????if(rotateArray.size()==0){
          ? ? ? ? ? ? return 0;
          ? ? ? ? }
          ? ? ? ? int min = rotateArray[0];
          ? ? ? ? for(int i=1;i<rotateArray.size();i++){
          ? ? ? ? ? ? if(rotateArray[i]<min){
          ? ? ? ? ? ? ? ? min = rotateArray[i];
          ? ? ? ? ? ? ? ? break;
          ? ? ? ? ? ? }
          ? ? ? ? }
          ? ? ? ? return min;
          ????}
          };

          發表于 2015-05-04 23:51:41 回復(20)
          import java.util.ArrayList;
          public class Solution {
              public int minNumberInRotateArray(int [] array) {
                  if(array.length == 0)
          			return 0;
                  int i = 0;
          		while (i < array.length - 1 && array[i] <= array[++i])
          			;
          		return i == array.length - 1 ? array[0] : array[i];
              }
          }
          我的思路是:首先數組長度為零時,返回零,因為測試要求這樣。然后有一個特殊情況是沒有旋轉,那么返回array[0],其次一般情況while一直循環,知道后面的數 < 前面的數停止,這個數就是我們要找的。

          發表于 2015-08-18 09:52:20 回復(7)
          import java.util.ArrayList;
          public class Solution {
          ? ? public int minNumberInRotateArray(int [] array) {
          ? ? if (array != null && array.length > 0) {
          int index1 = 0;
          int index2 = array.length - 1;
          int indexMid = index1;

          while (index1 <= index2) {
          indexMid = (index1 + index2) / 2;

          if (array[indexMid] == array[index2]
          && array[index1] == array[index2]) {

          int min = array[0];
          for (int i = 1; i < array.length; i++) {
          if (min > array[i]) {
          min = array[i];
          }
          }

          return min;
          }

          else if (array[indexMid] > array[index1]) {
          index1 = indexMid;
          } else {
          index2 = indexMid;
          }
          }

          return indexMid;
          } else {
          return 0;
          }
          ? ? }
          已經通過
          發表于 2015-08-15 17:46:48 回復(1)

          JavaScript

          看了排行第一大佬 念潤 的解法和其回復內泥點藥丸 的補充,得到如下解法:

          function minNumberInRotateArray(rotateArray) {
              var left = 0,
                  length = rotateArray.length,
                  right = length - 1,
                  mid;
              if (length == 0) { return 0; }
              while (rotateArray[left] >= rotateArray[right]) {
                  if (rotateArray[left] == rotateArray[right]) {
                      // 對left去重,使其指向最后一個重復的數字
                      for (var i = left; i < right; i++) {
                          if (rotateArray[left] != rotateArray[i]) {
                              left =i-1;
                              break;
                          }
                      }
                      // 對right去重,使其指向最前一個重復的數字
                      for (var i = right; i > left; i--) {
                          if (rotateArray[right] != rotateArray[i]) {
                              right = i+1;
                              break;
                          }
                      }
                  }
          
                  if (right - left <= 1) {
                      mid = right;
                      break;
                  }
                  // 四舍五入取整數,否則得到的就是小數,會報錯;
                  mid = Math.round(left + (right - left) / 2);
                  if (rotateArray[mid] >= rotateArray[left]) {
                      left = mid;
                  } else {
                      right = mid;
                  }
              }
              return rotateArray[mid];
          }
          編輯于 2019-05-07 19:52:50 回復(1)
          import java.util.ArrayList;
          public class Solution {
              public int minNumberInRotateArray(int [] array) {
                  if(array.length==0)
                      return 0;
                  else 
                      return partition(array,0,array.length-1);
              }
              //遞歸的目的是尋找亂序的子數組
              private int partition(int [] array,int start,int end){
                  if( array[start] < array[end] || start == end )  //如果第一個元素小于最后一個元素,說明數組從頭到尾都是非減的;如果只剩下一個元素,則直接返回
                      return array[start];
                  else {
                      int mid=start+(end-start)/2;
                      if( array[mid] < array[end]){    //如果中間值下于最后的值,說明后半部分為非減序列,所以在前半部分繼續尋找;
                                         //另外,之所以是mid而不是mid-1,是為了防止出現越界的情況,例如,array=[3,4],那么start=0,mid=0,end=1; (mid-1)等于-1,不可行
                          return partition(array,start,mid);
                      }else if(array[mid] == array[end]){    // 如果array=[1,0,1,1,1]或者[1,1,1,0,1],那沒辦法判斷亂序子數組的位置,所以只能削減一步
                          return partition(array,start,end-1);
                      }else{                //如果中間值大于最后值,那么說明亂序的部分在后半段,所以在后半段尋找。可以使用mid+1是因為,中間值都比最后值大了,那還要它干嘛?
                          return partition(array,mid+1,end);
                      }
                  }
              }
          }
          
          編輯于 2018-08-06 23:10:21 回復(1)
          C++實現,折半查找法
          class Solution {
          public:
          ? ? int minNumberInRotateArray(vector<int> rotateArray) {
          ? ? ? ? int length = rotateArray.size();
          ? ? ? ? if(length == 0)
          ? ? ? ? ? ? return 0;
          ? ? ? ? int pre = 0;
          ? ? ? ? int last = length - 1;
          ? ? ? ? while(pre < last)
          ? ? ? ? {
          ? ? ? ? ? ? int mid = (pre + last) / 2;
          ? ? ? ? ? ? if(rotateArray[mid] > rotateArray[last])
          ? ? ? ? ? ? {
          ? ? ? ? ? ? ? ? pre = mid + 1;
          ? ? ? ? ? ? }
          ? ? ? ? ? ? else if(rotateArray[mid] < rotateArray[last]){
          ? ? ? ? ? ? ? ? last = mid;
          ? ? ? ? ? ? }
          ? ? ? ? ? ? else{
          ? ? ? ? ? ? ? ? last = last - 1;
          ? ? ? ? ? ? }
          ? ? ? ? }
          ? ? ? ? return rotateArray[pre];
          ? ? }
          };
          
          

          發表于 2018-03-14 21:11:18 回復(1)
          //從兩端向中間進行遍歷
          import java.util.ArrayList;
          public class Solution {
          ? ? public int minNumberInRotateArray(int [] array) {
          ? ? ? ? if(array==null){
          ? ? ? ? ? ? ? return 0;
          ? ? ? ? ? }
          ? ? ? ??
          ? ? ? ? int minHand=0;
          ? ? ? ? int lHand=0;
          ? ? ? ? int rHand=array.length-1;
          ? ? ? ??
          ? ? ? ? while(lHand<rHand){
          ? ? ? ? ? ? if(array[lHand]<=array[lHand+1]){
          ? ? ? ? ? ? ? ? lHand=lHand+1;
          ? ? ? ? ? ? }else{
          ? ? ? ? ? ? ? ? minHand=lHand+1;
          ? ? ? ? ? ? ? ? break;
          ? ? ? ? ? ? }
          ? ? ? ? ? ??
          ? ? ? ? ? ? if(array[rHand]>=array[rHand-1]){
          ? ? ? ? ? ? ? ? rHand=rHand-1;
          ? ? ? ? ? ? }else{
          ? ? ? ? ? ? ? ? minHand=rHand;
          ? ? ? ? ? ? ? ? break;
          ? ? ? ? ? ? }
          ? ? ? ? }
          ? ? ? ??
          ? ? ? ? return array[minHand];
          ? ? }
          }
          發表于 2017-01-04 11:19:25 回復(1)
          # -*- coding:utf-8 -*-
          class Solution:
          ? ? def minNumberInRotateArray(self, rotateArray):
          ? ? ? ? # 可以使用min()函數, 但是在不適用min函數的情況下,思路應該是二分查找
          ? ? ? ? # 下面使用 遞歸實現2分查找,其中遞歸的時候必須使用return!!! 不然會返回none
          ? ? ? ? # write code here?
          ? ? ? ? start = 0
          ? ? ? ? end = len(rotateArray) - 1
          ? ? ? ? mid = int((start + end) / 2)
          ? ? ? ? if len(rotateArray) == 2:
          ? ? ? ? ? ? if rotateArray[0]>rotateArray[1]:
          ? ? ? ? ? ? ? ? return rotateArray[1]
          ? ? ? ? ? ? else:
          ? ? ? ? ? ? ? ? return rotateArray[0]
          
          ? ? ? ? elif rotateArray[mid] > rotateArray[end]:
          ? ? ? ? ? ? return self.minNumberInRotateArray(rotateArray[mid:end + 1])
          ? ? ? ? elif rotateArray[mid] < rotateArray[start]:
          ? ? ? ? ? ? return self.minNumberInRotateArray(rotateArray[start:mid + 1])
          

          發表于 2018-04-17 21:38:33 回復(4)
          微拍福利