<rp id="qpc6k"><optgroup id="qpc6k"><bdo id="qpc6k"></bdo></optgroup></rp>
  • <mark id="qpc6k"><noframes id="qpc6k"><b id="qpc6k"></b></noframes></mark>
    1. <input id="qpc6k"></input>
    <u id="qpc6k"></u>

      <video id="qpc6k"><input id="qpc6k"><p id="qpc6k"></p></input></video>
      <u id="qpc6k"><dl id="qpc6k"></dl></u>
      <b id="qpc6k"><kbd id="qpc6k"></kbd></b>

      首頁 > 試題廣場 > 旋轉數組的最小數字
      [編程題]旋轉數組的最小數字
      把一個數組最開始的若干個元素搬到數組的末尾,我們稱之為數組的旋轉。
      輸入一個非遞減排序的數組的一個旋轉,輸出旋轉數組的最小元素。
      例如數組{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)
      微拍福利