首页 > 代码库 > 154. Find Minimum in Rotated Sorted Array II (Array; Divide-and-Conquer)
154. Find Minimum in Rotated Sorted Array II (Array; Divide-and-Conquer)
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.
思路：有重复元素的时候，不能按I中这么分三类（反例：Input: [3,3,1,3]=>将roate in right判断成没有rotate）。解决方法是，当碰到nums[start]=nums[end]的情况时，end-1，寻找不同元素再进行二分法。
class Solution { public: int findMin(vector<int>& nums) { return dfs(nums,0,nums.size()-1); } int dfs(vector<int>& nums, int start, int end){ if(start==end) return nums[start]; if(nums[start]==nums[end]) return dfs(nums,start, end-1); int mid = start + ((end - start) >> 1); if(nums[mid] > nums[end]){ //rotate in the right return dfs(nums, mid+1,end); } else if(nums[start] <= nums[mid]){ //no rotate return nums[start]; } else{ //rorate in the left return dfs(nums, start, mid); } } };
154. Find Minimum in Rotated Sorted Array II (Array; Divide-and-Conquer)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。