首页 > 其他 > 详细

LeetCode 154. Find Minimum in Rotated Sorted Array II

时间:2015-02-24 00:47:28      阅读:344      评论:0      收藏:0      [点我收藏+]

二分搜索,和LeetCode 153. Find Minimum in Rotated Sorted Array相似。

只是在num[begin] == num[mid]时,需要binary_search(++ begin, end, num); 这时仅将begin移进一位,并没有进行二分查找。

所以如测试用例为 num = {1, 1, 1, 1, 1, ..., 1}等特殊情况时,最坏情况的时间复杂度为O(n).


代码:

class Solution 
{
public:
    int findMin(vector<int> &num) 
    {
        return binary_search(0, num.size()-1, num);
    }
private:
	int binary_search(int begin, int end, vector<int>& num)
	{
		if (num[begin] < num[end] || end - begin <= 1)
		{
			return min(num[begin], num[end]);
		} else if (num[begin] < num[(begin+end)>>1])
		{
			return binary_search(((begin+end)>>1)+1, end, num);
		} else if (num[begin] > num[(begin+end)>>1])
		{
			return binary_search(begin, (begin+end)>>1, num); 
		} else
		{
			return binary_search(++begin, end, num);
		}
	}
};


LeetCode 154. Find Minimum in Rotated Sorted Array II

原文:http://blog.csdn.net/stephen_wong/article/details/43920107

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!