33.搜索旋转排序数组

上来先ac了再说，用时32ms

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except Exception:
            return -1

然后改用二分的思路。首先二分查找旋转点，然后旋转点把数据一分为二，在对应的数据里继续二分查找

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        if len(nums) == 1:
            return 0 if nums[0] == target else -1
        r = 0
        if nums[0] > nums[-1]: # 从中间旋转
            i, j = 0, len(nums) -1
            while True:
                if nums[i] > nums[i+1]:
                    index = i
                    break
                if nums[j] < nums[j-1]:
                    index = j -1
                    break
                k = (i + j) // 2
                if nums[k] > nums[0]:
                    i = k
                else:
                    j = k
            # 二分
            if target < nums[0]:
                r = index + 1
                nums = nums[index+1:]
            else:
                r = 0
                nums = nums[:index+1]
        i = 0
        j = len(nums)-1
        while True:
            if nums[i] == target:
                return r + i
            if nums[j] == target:
                return r + j
            if i + 1 >= j:
                return -1
            k = (i + j) // 2
            if nums[k] > target:
                j = k
            else:
                i = k

感觉思路是二分没问题，但是提交了之后发现执行速度（36ms）还不如第一种方式，感觉是因为赋值耗时，优化了一下代码，速度变成28ms

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        if len(nums) == 1:
            return 0 if nums[0] == target else -1
        r = 0
        i = 0
        j = len(nums)-1
        if nums[0] > nums[-1]: # 从中间旋转
            i, j = 0, len(nums) -1
            while True:
                if nums[i] > nums[i+1]:
                    index = i
                    break
                if nums[j] < nums[j-1]:
                    index = j -1
                    break
                k = (i + j) // 2
                if nums[k] > nums[0]:
                    i = k
                else:
                    j = k
            # 二分
            if target < nums[0]:
                r = 0
                i = index + 1
                j = len(nums)-1
            else:
                r = 0
                i = 0
                j = index
        while True:
            if nums[i] == target:
                return r + i
            if nums[j] == target:
                return r + j
            if i + 1 >= j:
                return -1
            k = (i + j) // 2
            if nums[k] > target:
                j = k
            else:
                i = k

同样的代码提交了几次执行时间也不完全一致，应该是leetcode后台的原因。 看了下题解，还有其他的思路

评论