首页 > 代码库 > 【LeetCode】Find Minimum in Rotated Sorted Array 在旋转数组中找最小数
【LeetCode】Find Minimum in Rotated Sorted Array 在旋转数组中找最小数
Add Date 2014-10-15
Find Minimum in Rotated Sorted Array
Suppose a sorted array 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.
这个很简单，因为没有重复数字，数组本质上还是有序的，用类似二分查找的方法复杂度O(log n)。code 也没几行，直接看 code 吧，记得考虑一下整个数组没有 rotated 的情况。
1 class Solution { 2 public: 3 int findMin(vector<int> &num, int pre, int post) { 4 if(pre == post) 5 return num[pre]; 6 if(num[pre] < num[post]) 7 return num[pre]; 8 int mid = (pre+post)/2; 9 if(num[mid] >= num[pre])10 return findMin(num, mid+1, post);11 if(num[mid] < num[post])12 return findMin(num, pre, mid);13 }14 int findMin(vector<int> &num) {15 int len = num.size();16 return findMin(num, 0, len-1);17 }18 };
明天继续刷LeetCode。。
【LeetCode】Find Minimum in Rotated Sorted Array 在旋转数组中找最小数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。