6、旋转数组
[3,4,5,1,2] 返回值
1 1、常规做法
int minNumberInRotateArray(vector
rotateArray) { if (rotateArray.size() == 0) return 0; int minNum = rotateArray[0], len = rotateArray.size(); for (int i = 1; i < len; ++i) { if (rotateArray[i] < minNum) return rotateArray[i]; } return minNum; }
int minNumberInRotateArray(vector
rotateArray) { if (rotateArray.size() == 0) return 0; int len = rotateArray.size(); for (int i = 0; i < len-1; ++i) { if (rotateArray[i] > rotateArray[i+1]) return rotateArray[i+1]; } return rotateArray[0]; }
2、二分法 很不错
int minNumberInRotateArray(vector
rotateArray) { if (rotateArray.size() == 0) return 0; int low = 0, high = rotateArray.size() - 1; while (low + 1 < high) { int mid = low + (high - low) / 2; if (rotateArray[mid] < rotateArray[high]) high = mid; else if (rotateArray[mid] == rotateArray[high]) high = high-1; else { low = mid; } } return min(rotateArray[low], rotateArray[high]); }
二刷：
2-1常规做法
运行时间：26ms 占用内存：1124k
int minNumberInRotateArray(vector<int> rotateArray) {
if( rotateArray.size() == 0) return 0; if( rotateArray.size() == 1) return rotateArray[0]; for(int i = 0; i < rotateArray.size()-1; ++i){
if( rotateArray[i] > rotateArray[i + 1] ) return rotateArray[i+1]; } return rotateArray[0];//走到这一步了，就说明整个数组都是递增或者都是非递减的 } 2-2、二分法变种
int minNumberInRotateArray(vector<int> rotateArray) {
if( rotateArray.size() == 0) return 0; int low = 0, high = rotateArray.size()-1; while(low + 1 < high){
int mid = low + (high - low)/2; if(rotateArray[mid] < rotateArray[high]) high = mid;//说明右边有序，那就向左边走 else if(rotateArray[mid] == rotateArray[high]) high = high-1;// 这种情况跟是特例只能一个一个的判断 else low = mid; } return min(rotateArray[low], rotateArray[high]); } 美女帅哥们如果觉得写的还行，有点用的话麻烦点个赞或者留个言支持一下阿秀~
如果觉得狗屁不通，直接留言开喷就完事了。
需要该笔记PDF版本的去个人公众号【拓跋阿秀】下回复“阿秀剑指offer笔记”即可。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208811.html原文链接：https://javaforall.net
