暴力解法
直接一次扫描找出最小元素, 时间效率比较低, 需要改进
- class Solution {
- public:
- int minNumberInRotateArray(vector<int> arr) {
- int min = INT_MAX;
- for(int i=0;i<arr.size();i++)
- {
- if(arr[i]<min)min = arr[i];
- }
- return min;
- }
- };
二分查找法
- class Solution {
- public:
- int minNumberInRotateArray(vector<int> arr) {
- int left = 0;
- int right = arr.size()-1;
- int mid = (left+right)/2;
- while(left != mid)
- {
- if(arr[left]>arr[mid]){
- right = mid;
- }else if(arr[mid]>arr[right]){
- left = mid;
- }
- mid = (left+right)/2;
- }
- return arr[right];
- }
- };
发现提交测试的时间还是一样的, 可能是测评系统的问题吧, 使用了二分查找多少都会快一些吧
来源: http://www.bubuko.com/infodetail-3392855.html