Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
思路：本题思路主要是使用分治思想，想要找整个数列的最小值，就是找到小于每一个数的值，因此我们把原来的数组划分为小于某一个数pivot的小数组，每个小数组用同样的想法进行划分，直到小数组大小为0，这样用于划分的数pivot就是我们需要的数。pivot的取法类似于快排。
int min(vector<int> &nums, int pivot) {
vector<int>left;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] < pivot) {
left.push_back(nums[i]);
}
}
if (left.size() == 0) {
return pivot;
}
return min(left, left[0]);
}
class Solution {
public:
int findMin(vector<int>& nums) {
if (nums.size() == 1) {
return nums[0];
}
return min(nums, nums[0]);
}
};
转载请注明原文地址: https://ju.6miu.com/read-35612.html
