首页 > 代码库 > 【LeetCode】Find Minimum in Rotated Sorted Array II (2 solutions)
【LeetCode】Find Minimum in Rotated Sorted Array II (2 solutions)
Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
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.
The array may contain duplicates.
解法一：暴力解法，直接使用algorithm库中的求最小元素函数
需要遍历整个vector
class Solution {public: int findMin(vector<int> &num) { if(num.empty()) return 0; vector<int>::iterator iter = min_element(num.begin(), num.end()); return *iter; }};
解法二：利用sorted这个信息。如果平移过，则会出现一个gap，也就是从最大元素到最小元素的跳转。如果没有跳转，则说明没有平移。
比上个解法可以省掉不少时间，平均情况下不用遍历vector了。
class Solution {public: int findMin(vector<int> &num) { if(num.empty()) return 0; else if(num.size() == 1) return num[0]; else { for(vector<int>::size_type st = 1; st < num.size(); st ++) { if(num[st-1] > num[st]) return num[st]; } return num[0]; } }};
【LeetCode】Find Minimum in Rotated Sorted Array II (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。