题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路
利用二分查找的思想，设定三个指针：first、mid、last。若mid指向的数字大于或等于first，意味着前半部分是非递减序，最小数字肯定在后半部分，所以first指向mid；若mid指向的数字小于或等于last，意味着后半部分是非递减序，最小数字肯定在前半部分，所以last指向mid。保持first指向数字大于或等于last，这样循环下去直到first和last指向相邻数字，那么last指向数字即为最小。注意若first、mid、last三者指向数字均相同，则无法判断最小数字在哪部分，所以只能顺序查找。
代码
class Solution { public: int minNumberInRotateArray(vector<int> rAr) { if(rAr.size() == 0) return 0; int first = 0, len = rAr.size(); int last = len - 1; int mid = first; while(rAr[first] >= rAr[last]){ if(first+1 == last){ mid = last; break; } mid = (first + last) / 2; if(rAr[mid] == rAr[first] && rAr[mid] == rAr[last]){ int minn = rAr[mid]; for(int i = first; i <= last; i++){ if(rAr[i] < minn) mid = i; } break; } if(rAr[mid] >= rAr[first]){ first = mid; } else if(rAr[mid] <= rAr[last]){ last = mid; } } return rAr[mid]; } };
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
