LeetCode 153. Find Minimum in Rotated Sorted Array寻找旋转排序数组中的最小值 (C++)

概述题目： 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 d 题目：

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,7,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

input: [3,2] Output: 1

Example 2:

input: [4,2]Output: 0

分析：

给定了一个升序排序的数组且在某个点上进行了旋转。也就是[1,3,5]可能变成[3,2]。求其中的最小元素，且数组中没有重复元素。

遍历一遍数组直接求得最小元素，时间复杂度时O(n)，不过很明显，题目中给定的数组是“有序的”，我们可以利用这个特点来更快的求解此问题。

如果给定一个有序数组(无旋转的)，我们可以立刻知道数组中最小的元素就是第一个元素，而在这道题中，我们可以使用二分法来求解，而且每一次分割，必定会产生一个有序数组，和一个有可能有序的数组。

比如：[4,2]如果分割成[4,7]和[0,2]，两个都是有序数组，我们可以立刻知道他们两个的最小值是4和0，再求一次min即可。当然这是最好的情况，即一次分割两个数组均有序。

当然大多数情况可能是其中一个有序，另一个是旋转有序的。

例如：[4,6]和[7,2]，左侧的数组是有序的，右侧是旋转有序的，那么左面我们可以立刻得到最小值4，右侧则继续二分求解即可。

判断数组是否有序很简单，即数组左侧的元素是否小于右侧的，如果小于，则数组有序。

当数组剩两个元素的时候直接返回其中的最小值即可。

程序：

class Solution {public:    int findMin(vector<int>& nums) {        if(nums.size()==1) return nums[0];        int l = 0;        int r = nums.size()-1;        return find(nums,l,r);    }    int find(vector<int>& nums,int l,int r){        if(nums[l] < nums[r] || l==r) return nums[l];        if(r-l == 1) return min(nums[l],nums[r]);        int mID = (l+r)/2;        return min(find(nums,mID-1),find(nums,mID,r));    }};

总结

以上是内存溢出为你收集整理的LeetCode 153. Find Minimum in Rotated Sorted Array寻找旋转排序数组中的最小值 (C++)全部内容，希望文章能够帮你解决LeetCode 153. Find Minimum in Rotated Sorted Array寻找旋转排序数组中的最小值 (C++)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。