Leetcode 33/81

Posted on | | 阅读数
Words count in article: 412 | Reading time ≈ 2

Question1

Solution1

二分查找。

因为列表被rotated了，不能用普通二分查找的判断条件来判断了。

按照mid进行分割后。对于前半段，考虑其first和mid之间的大小关系。

如果first小于mid，那么这一段数据是排序好的，这时候判断target是否在其中，如果在，则将last=mid-1，继续进行。如果不在，那么说明target在后半段，first=mid+1。

如果first大于mid，那么后半段为排序好的数列，考虑target时候在其中，如果在，则将first=mid+1，继续进行。如果不在，那么说明target在前半段，last=mid-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        first, last = 0, len(nums) - 1
        while first <= last:
            mid = (first + last) // 2
            if nums[mid] == target:
                return mid
            elif nums[first] <= nums[mid]:
                if nums[first] <= target <= nums[mid]:
                    last = mid - 1
                else:
                    first = mid + 1
            else:
                if nums[mid] <= target <= nums[last]:
                    first = mid + 1
                else:
                    last = mid - 1
        return -1

Solution2

直接查找。

1
2
3
4
5
6
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

Question2

Solution1

修改上面的代码。去除nums开头与末位相同的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums:
            return False
        first, last = 0, len(nums) - 1
        while first < last and nums[first] == nums[last]:
            first += 1
        while first <= last:
            mid = (first + last) // 2
            if nums[mid] == target:
                return True
            elif nums[first] <= nums[mid]:
                if nums[first] <= target <= nums[mid]:
                    last = mid - 1
                else:
                    first = mid + 1
            else:
                if nums[mid] <= target <= nums[last]:
                    first = mid + 1
                else:
                    last = mid - 1
        return False

Solution2

直接查找。

1
2
3
4
5
6
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return True
        return False