153. Find Minimum in Rotated Sorted Array

2019-11-08 03:02:36

字体：大中小

来源：转载

供稿：网友

题目

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.

Subscribe to see which companies asked this question.

思路

两种情况，一种第一个比最后一个小，直接返回第一个。另一种移位了，最小的在中间，折半和第一个元素比较。

代码

class Solution {public: int findMin(vector<int>& nums) { //两种情况，一种第一个比最后一个小，直接返回第一个 //另一种移位了，最小的在中间，折半和第一个元素比较 int length = nums.size(); if(length == 0) { return 0; } if(length == 1) { return nums[0]; } if(nums[0] < nums[length-1]) { return nums[0]; } //这要从下标1开始，nums[0]此时肯定不是最小的，不能参与排序，不然当最后middle==0时可能会出问题 return getMinElement(nums,1,length-1,nums[0]); } int getMinElement(vector<int>&nums,int begin,int end,int compareNum) { if(begin >= end) { return nums[begin]; } //防止溢出 int middle = begin + (end - begin)/2; if(nums[middle] > compareNum) { return getMinElement(nums,middle+1,end,compareNum); } else { //返回当前数字和另一半求得值得最小值 return min(nums[middle],getMinElement(nums,begin,middle-1,compareNum)); } }};

上一篇：【SQL Server】体系结构

下一篇：PAT 1036