Leetcode 153. Find Minimum in Rotated Sorted Array

2019-11-11 04:06:25

字体：大中小

来源：转载

供稿：网友

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.

You may assume no duplicate exists in the array.

s思路： 1. 一看就是binary search。找中点，然后把中点和左右两个端点比较：如果中间大于左测且小于右测，说明是正常排序，那么直接取最左侧点；如果中点大于右侧，说明左边是排好序的，所以最小值应该在右侧；如果中点小于左侧，说明右侧排好序，最小值在左侧。这里写图片描述 2. 看上图，之前做binary search画的。如果mid>=left,说明左侧是连续递增的，同时还说明最小值在[mid+1,right]之间；如果mid<=right,说明右侧连续递增，同时说明最小值在[left,m]之间。这里强调一点，在前面一种情况，mid觉不可能是最小值，因为mid还大于left，而left还大于right；后一种情况下，mid就可能取得最小值，因为mid<=right,所以mid就可能是最小值！

class Solution {public: int findMin(vector<int>& nums) { // int l=0,r=nums.size()-1; while(l<=r){ int m=l+(r-l)/2; if(nums[m]>=nums[l]&&nums[m]<=nums[r]) return nums[l]; if(nums[m]<=nums[r]){//判断右边是递增 r=m;//m这个位置可能是最小值 }else if(nums[m]>=nums[l]){//判断左边是递增 l=m+1; } } return 0; }};

上一篇：PAT BASIC 1005

下一篇：KMP算法的初级扩展应用