资讯专栏INFORMATION COLUMN

leetcode-33-Search in Rotated Sorted Array

SKYZACK / 859人阅读

摘要:由于不是一直升序,所以需要多些条件进行范围的限定。注意边界值的确定,有边界值相等,列表只有一个值,这些情况。注意的使用应用排序,快速确定某个值的位置

题目阐释:
给定一组升序数组,取某个点之后将数组截断交换前后两个数组顺序,
给定一个值,求这个值的index
重点:二分法,确定target在哪个列表中,之后不断二分法进行位置确认。
   由于不是一直升序,所以需要多些条件进行范围的限定。
   二分法,需要不断 mid-1或者mid+1,因为mid已经判断过,没有再出现在数组的意义。  
   注意边界值的确定,有 边界值相等,列表只有一个值,这些情况。注意 <  <=的使用
  
应用:排序,快速确定某个值的位置
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        start,end=0,len(nums)-1
        # mid=(start+end)//2+1
        while True:
            mid=(start+end)//2
            if mid>end:
                return -1
            if nums[mid]==target:
                return mid
            if end<=start:
                return -1
            if nums[start]<=target<=nums[mid] or nums[mid]           
               
                                           
                       
                 

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/42148.html

相关文章

  • leetcode33 search in rotated sorted array

    摘要:这里相比于思路一,更适用于目标节点在中间的情况,而思路一在目标节点分布在数组两侧会效率更高。 题目要求 Suppose an array sorted in ascending order 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 ...

    MkkHou 评论0 收藏0
  • leetcode 33 Search in Rotated Sorted Array

    摘要:如正常的升序排列应该是,,,,,,旋转过后可能就是,,,,,,。想法因为这是一个经过旋转的升序数组,我们可以将其看作两个升序的序列,,,和,,。如果在前一个序列,则从前面进行查找。如果在后面一个序列,则从最后一个元素开始查找。 题目详情 Suppose an array sorted in ascending order is rotated at some pivot unknown...

    diabloneo 评论0 收藏0
  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

    摘要:排序数组中找最小值或最大值的题目,很明显可以使用二分法。因此,只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个,中点值和末位相等。此时,两边同时递归,并返回两边递归值的较小值。当首位和末位重合,说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

    cgh1999520 评论0 收藏0
  • Find Minimum in Rotated Sorted Array

    摘要:题目思路个人觉得这是一道值得回味的二分法题目。与给出的二分法搜索比,这道题目的是未知的,并且是。我个人是从观察给出的例子入手的。我本人走的弯路是,过于专注于,从而逻辑变得复杂。其实,,和步就可以帮助我们顺利找到最小值。 题目 http://www.lintcode.com/en/pr... Suppose a sorted array is rotated at some pivot ...

    DataPipeline 评论0 收藏0
  • [Leetcode] Find Minimum in Rotated Sorted Array 找旋

    摘要:二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点,实际上类似找一个山谷,只要两边都比中间高就对了,这和这题很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...

    notebin 评论0 收藏0

发表评论

0条评论

SKYZACK

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<