153. Find Minimum in Rotated Sorted Array

2019-11-08 03:02:36

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

題目

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 { //返回當前數(shù)字和另一半求得值得最小值 return min(nums[middle],getMinElement(nums,begin,middle-1,compareNum)); } }};

上一篇：【SQL Server】體系結(jié)構(gòu)

下一篇：PAT 1036