👋Hi~ o(￣▽￣)ブ這里是豬豬程式員
👀 很高興見到你O(∩_∩)O！
🌱 現在正在發芽中…
💞? 博主水平有限，如果發現錯誤，一定要及時告知作者哦 o(￣︶￣)o！感謝感謝！
📫博主的碼云 gitee，平常博主寫的程式代碼都在里面，
??這是一個新的專欄??我希望自己能夠堅持把《劍指offer》這本書的題目刷完，
劍指 Offer 11. 旋轉陣列的最小數字
- 分析
- 方法一:暴力求解法（執行用時：0 ms 記憶體消耗：5.5 MB）
- 方法二:二分法（執行用時：0 ms 記憶體消耗：5.5 MB）
- 情況一：當沒有重復數字的時候
- 情況二：當有重復數字的時候
- 總結
??題目來源
把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，輸入一個遞增排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，例如，陣列 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該陣列的最小值為1，
示例 1：
輸入：[3,4,5,1,2]
輸出：1
示例 2：
輸入：[2,2,2,0,1]
輸出：0
分析
剛開始看這個旋轉陣列的時候有點模糊，仔細想了想，我的解釋如下：
陣列剛開始是有序的，但可能有重復的數字
接著按任意點將其旋轉，旋轉過后陣列就變成有序的兩個部分，但從哪里開始旋轉是任意的
因此這種要旋轉一遍的陣列就是旋轉排序陣列
題目要求：找到這種旋轉陣列當中最小的數字
方法一:暴力求解法（執行用時：0 ms 記憶體消耗：5.5 MB）
演算法
1.從下標為0的元素開始遍歷
2．每次進行比較，如果當前元素比相鄰的下一個元素大，則對應的下一元素即為最小值.如果查到最后一個元素都沒有出現這種情況，則下標為0的元素為最小元素(因為此時說明陣列中有重復的元素)
int minArray(int* numbers, int numbersSize){
int i,j;
int min=numbers[0];
for(i=0;i<numbersSize;i++)
{
if(min>numbers[i])
{
min=numbers[i];
}
}
return min;
}
方法二:二分法（執行用時：0 ms 記憶體消耗：5.5 MB）
一般二分查找的程序介紹
1．找到中間的關鍵字
2.比較查找的關鍵字與中間關鍵字的大小關系
3．如果相等就相當于已經找到
4．如果查找的關鍵字小于中間的關鍵字則在前半部分進行同樣的程序（從小到大存盤)
5．如果查找的關鍵字大于中間的關鍵字則在后半部分進行同樣的程序（從小到大存盤)
一般二分查找的要求
1.順序存盤
2.元素有序
原因
1．通過下標即可得到關鍵字
2．任取一個關鍵字的值即可確定所尋找關鍵字是在它前面還是后面
演算法
1.從下標為0的元素開始遍歷
2．每次進行比較，如果當前元素比相鄰的下一個元素大，則對應的下一元素即為最小值.如果查到最后一個元素都沒有出現這種情況，則下標為0的元素為最小元素(因為此時說明陣列中有重復的元素)
情況一：當沒有重復數字的時候
如果numbers[mid]>numbers[right],則前半部分一定是順序的，最小值(分界點)在mid后面
因此我們就可以縮小查找范圍，直接到mid后面找最小的元素
如果numbers[mid]<numbers[right],則后半部分一定是順序的，最小值(分界點)在mid前面
因此我們就可以縮小查找范圍，直接到mid前面找最小的元素
情況二：當有重復數字的時候
會出現numbers[mid]== numbers[right]的情況
此時我們并不能確定到底分界點出現在mid的前面還是后面
解決方法：暴力地從右到左進行遍歷，知道mid指標的元素小于right指標的元素
int minArray(int* numbers, int numbersSize){
int left=0,right=numbersSize-1,mid;
while(left<right)
{
mid=left+(right-left)/2;
if(numbers[mid]<numbers[right])
{
right=mid;
}
else if(numbers[mid]>numbers[right])
{
left=mid+1;
}
else
{
right--;
}
}
return numbers[left];
}
總結
感覺暴力法好簡單呀哈哈哈
最后，我想在這里記錄一下我的生活：
最近我早上是5點四十起床
看到了早晨六點的教室，晚上是十點回宿舍，因為阿姨會趕人嗚嗚嗚~
還找到了一個一起努力的學長，突然感覺自己也挺幸福的呀，看看我們之間的對話：
所以小豬豬一定要往前沖呀！！！！！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/297626.html
標籤：其他