Find Minimum in Rotated Sorted Array I II

Find Minimum in Rotated Sorted Array I

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

解题思路:

求一个已经排好序的数组旋转之后的最小值,,且该数组中无重复元素。因为是按升序排好序的数组旋转,则旋转之后新数组为 升序—-突然变小—–升序。则我们找到突然变小的那个数字即可,那就是最小值,代码如下:

class Solution {public:int findMin(vector<int>& nums) {if(nums.size()==1) return nums[0];if(nums.size()==2){return min(nums[0],nums[1]);}int min=nums[0];for(int i=0;i<nums.size()-1;i++){if(nums[i]>nums[i+1])min=nums[i+1];}return min;}};

Find Minimum in Rotated Sorted Array II

和I 相同,也是找旋转之后数组的最小值,但是数组中可能会有重复元素

解题思路:方法一:

因为有无重复元素,数组开始是升序排序的没变,则旋转之后升序—-突然变小—–升序这个规律也没变,跟I 一样,我们采用相同的方法,只是需要考虑要是所有元素都相同的情况,这是我们输出任何一个元素都可以。代码如下:

class Solution {public:int findMin(vector<int>& nums) {if(nums.size()==1) return nums[0];if(nums.size()==2) return min(nums[0],nums[1]);for(int i=0;i<nums.size()-1;i++){if(nums[i+1]<nums[i])return nums[i+1];}return nums[0];}};方法二:

旋转之后的数组有 升序—-突然变小—–升序 的规律,找最小元素(最小元素位于数组中间)我们可以用前后向中间移动的方法,加快脚步。要住的就是,如果遇到重复元素,我们需要特殊处理。代码如下:

class Solution {public:int findMin(vector<int>& nums) {if(nums.size()==0) return 0;int low=0,high=nums.size()-1;while(low<high){int mid=(low+high)/2;if(nums[mid]>nums[high])low=mid+1;else if(nums[mid]<nums[high])high=mid;else{if(nums[mid]==nums[low]){low++;high–;}elsehigh–;}}return nums[high];}};

坚韧是成功的一大要素,只要在门上敲得够久够大声,终会把人唤醒的。

Find Minimum in Rotated Sorted Array I II

相关文章:

你感兴趣的文章:

标签云: