?？皖}霸 [ 旋轉數組的最小數字] C++題解/答案

題目描述

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。
輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。
NOTE：給出的所有元素都大于0，若數組大小為0，請返回0。

題解：

兩種方法：
第一種很簡單，直接一遍循環找到最小值，這種方法大家都會
我們介紹第二種二分
二分就像查字典一樣,先翻最中間一頁，如果目標單詞比我們所翻單詞大，說明目標單詞在右邊，反之在左邊，假如在右邊，我們就進行一樣的操作，繼續中間翻，然后判斷左右
二分答案，就是用二分的方法，在可能的答案區間里找出問題的答案，大多數情況下用于求解滿足某種條件下的最大（小）值，前提是答案具有單調性，同時也可以理解為是一種倒推方法（先找答案在判斷答案是否可行、有沒有更優解）。

代碼：

class Solution { public:int minNumberInRotateArray(vector<int> rotateArray) {int maxn=1e9;for(int i=0;i<rotateArray.size();i++){maxn=min(maxn,rotateArray[i]);}return maxn;} };

二分法：

class Solution { public:int minNumberInRotateArray(vector<int> rotateArray) {if(rotateArray.empty())return 0;int low = 0;int hight = rotateArray.size() - 1;int mid = 0;while(low < hight){mid = low + (hight - low)/2;if(rotateArray[mid] >= rotateArray[hight])low =mid +1;elsehight = mid;}return rotateArray[hight];} };

總結

以上是生活随笔為你收集整理的牛客题霸 [ 旋转数组的最小数字] C++题解/答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。