leetcode 【 Find Minimum in Rotated Sorted Array II 】python 实现

题目：

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.

代码：oj测试通过 Runtime: 82 ms

 class Solution:

     # @param num, a list of integer

     # @return an integer

     def findMin(self, num):

         # none case

         if num is None :

             return None

         # only one element case

         if len(num)==1 :

             return num[0]

         # binary search case

         start = 0

         end = len(num)-1

         while start<end and num[start]>=num[end]:

             mid = (start+end)/2

             if num[start]>num[end]:

                 if num[mid]>num[end] :

                     start = mid+1

                 else:

                     end = mid

             else:

                 if num[mid]>num[end] :

                     start = mid+1

                 else :

                     start = start+1

         return num[start]

思路：

对比之前一道题：http://www.cnblogs.com/xbf9xbf/p/4261334.html

这道题需要考虑duplicate的case。

简略地说，跟之前不带duplicate的case相比，核心的区别在：

不带duplicate的case : num[start]>num[end]是铁定成立的

带duplicate的case : num[start]>num[end]不一定是成立的，还可能是num[start]==num[end]

就是多了这么一个等号的可能，所以最直观的办法就是单独把这种等号的情况拿出来嘛。

因此需要讨论的情况一共有两种：

1. num[start]>num[end]

2. num[start]==num[end]

有人可能要问，为啥不能有num[start]<num[end]的情况？答：因为在while循环终止条件中已经限定了num[start]>=num[end]；如果真有num[start]<num[end]的情况，那么当前start到end位置的数组已经是有序的了，直接return[start]就OK了。

Tips:

在AC之前还遇上几个问题：

1. 如果出现无法判断最小值是在左半边还是右半边的时候，不要同时start=start+1 end=end-1，start=start+1即可，否则会指针溢出

2. 之前在while循环条件的时候，一直写的是start<=end。就是多了这么一个等号，submit了几次一直不能AC。究其原因，如果start==end，就会导致执行start=start+1语句，不是溢出就是错。如果修改一下while循环的条件，start<end，那么当start==end的时候自动就退出循环了，并且返回num[start]了。

巴特西

leetcode 【 Find Minimum in Rotated Sorted Array II 】python 实现

最新文章

热门文章