剑指offer-旋转数组的最小数字

2019-11-06 07:54:20

字体：大中小

来源：转载

供稿：网友

问题

题目：[旋转数组的最小数字]

思路

需要注意这几个点：

旋转数组将原数组分为两部分，前面的有序子数组和后面的有序子数组前面的有序子数组比后面的有序子数组大。这是基本的性质。所以对于旋转后的数组，一定有第一个元素比最后一个元素大的性质。当然，存在例外的情形。旋转0个，就是原数组。[1,0,1,1,1]和[1,1,1,0,1]的情形。此时无法确定中间的元素到底数组第一个还是第二个数组，因此会导致结果不同。对于上面这种情形，最后的解可能出现在前面也可能出现在后面。

基本的解法就是判断，

arr[low] <= arr[mid]，证明arr[mid]在前半个子数组，此时更新low=mid；否则，arr[mid]在后半个数组，此时更新high=mid.最终结束迭代的情形时 low + 1 = high，此时arr[high]就是最小元素。

代码

/*这题的关键就是右侧的数组肯定比左侧的小*/class Solution {public: int minNumberInRotateArray(vector<int> rotateArray) { int sz = rotateArray.size(); if(!sz) return -1; vector<int>& arr = rotateArray; if(1==sz) return arr[0]; if(arr[0] < arr[sz-1]) return arr[0]; // 防止旋转0个 int low = 0; int high = sz-1; while(low+1 < high){ int mid = (low+high)/2; if(arr[low] == arr[mid] && arr[mid] == arr[high]){ // 防止[1,2,1]的情形，必须加上中间元素 int min = arr[low]; for(int i = low+1; i <= high; ++i){ if(arr[i] < min) min = arr[i]; } return min; } if(arr[low] <= arr[mid]) low = mid; else high = mid; } return arr[high]; }};

上一篇：堆排序

下一篇：第二次实验（实验报告博客）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注