Find Minimum in Rotated Sorted Array II

Description:

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.

Code:

bool flag = true;int findMin(vector<int>& nums) {if (nums.size()==0){flag = false;return 0;}int left = 0;int right = nums.size()-1;while (left < right){int mid = (left + right)/2;if (nums[mid] < nums[right])right = mid;else if (nums[mid] > nums[right])left = mid+1;else{//此时不能判最小值在左边还右边，遍历判断int result = nums[left];for (int i = left+1; i <= right; i++){if ( nums[i] < result)result = nums[i];}return result; }}return nums[left];}

 

转载于:https://www.cnblogs.com/happygirl-zjj/p/4592202.html

总结

以上是生活随笔为你收集整理的Find Minimum in Rotated Sorted Array II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。