找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1325|回复: 0
收起左侧

[刷题记录板] [leetcode] (Dec,15)每天两道题目,配 python参考解答

[复制链接]

20

主题

5

精华

586

积分

超级会员

Rank: 4

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

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

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

x
题目(一):Search 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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.


题目(二):Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.




图片割开参考答案:

题目(一):                                                      题目(二):








python参考解答:
题目(一):Search in Rotated Sorted Array
[code]class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return an integer
    def search(self, A, target):
        left = 0; right = len(A) - 1
        while left <= right:
            mid = (left + right) / 2
            if target == A[mid]:
                return mid
            if A[mid] >= A[left]:
                if target < A[mid] and target >= A[left]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif A[mid] < A[right]:
                if target > A[mid] and target <= A[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1[/code]
题目(二):Search in Rotated Sorted Array II
[code]class Solution:
    # @param A a list of integers
    # @param target an integer
    # @return a boolean
    def search(self, A, target):
        left=0; right=len(A)-1
        while left<=right:
            mid=(left+right)/2
            if A[mid]==target: return True
            if A[left]==A[mid]==A[right]:
                left+=1; right-=1
            elif A[left]<=A[mid]:
                if A[left]<=target                 else: left=mid+1
            else:
                if A[mid]<=target                 else:right=mid-1
        return False[/code]

本帖被以下淘专辑推荐:

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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