找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1899|回复: 1
收起左侧

[米群网刷题小分队] 【Find Minimum in Rotated Sorted Array】(Dec,7)每天两道,python解答参考

[复制链接]

20

主题

5

精华

586

积分

超级会员

Rank: 4

积分
586
发表于 12-7-2014 12:03 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目(一):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.



题目(二):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.


图片割开参考答案:
题目(一):                                                              题目(二):









python参考解答:

题目(一):Find Minimum in Rotated Sorted Array
[code]class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        L = 0; R = len(num)-1
        while L < R and num[L] > num[R]:
            M = (L+R)/2
            if num[M] < num[R]:
                R = M
            else:
                L = M+1
        return num[L][/code]

题目(二):Find Minimum in Rotated Sorted Array II
[code]class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        L = 0; R = len(num)-1
        while L < R and num[L] >= num[R]:
            M = (L+R)/2
            if num[M] > num[L]:
                L = M + 1
            elif num[M] < num[R]:
                R = M
            else:
                L += 1
        return num[L][/code]

本帖被以下淘专辑推荐:

18

主题

9

精华

522

积分

新米人

Rank: 1

积分
522
发表于 12-7-2014 12:11 PM | 显示全部楼层
顶一下,很少看见python的解法
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表