假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2] 输出: 1示例 2:
输入: [4,5,6,7,0,1,2] 输出: 0
解法一：
//时间复杂度O(logn), 空间复杂度O(logn)
class Solution {
public:
int findMin(const vector<int>& nums, int left, int right) {
if(nums[left] <= nums[right]) return nums[left];//整体有序，返回最左边的元素
int mid = left + (right - left) / 2;
return nums[left] > nums[mid] ? findMin(nums, left, mid) : findMin(nums, mid + 1, right);//继续查找无序子序列
}
int findMin(vector<int>& nums) {
return findMin(nums, 0, nums.size() - 1);
}
};
解法一：
对数组nums的子序列[left, right]进行查找，如果整个子序列有序（nums[left] <= nums[right]），直接返回nums[left]；
否则就是部分有序（nums[left] > nums[mid]？），选择无序的那一部分，继续进行查找，直到查找的子序列有序。
2019/12/30 13:00