Day 6 | 7/3

[tech-cow]

今天任务以下题目：

今日任务 (Binary Search)

• Binary Search最后一天，完成总结帖

刷题

Leetcode

• 240. Search a 2D Matrix II
• 33. Search in Rotated Sorted Array
• 81. Search in Rotated Sorted Array II

[tech-cow]

Leetcode

240. Search a 2D Matrix II

类型：考虑边界
Time Complexity O(m + n)
Time Spent on this question: 20 mins

这题放弃直接看的最高票答案，方法聪明到让我无fuck说。直接用target和矩阵中的每个row的最后一个值比对。因为每个row都是排序过的，也就是说最后一个值一定是该row最大的值，所以只要target值比这个最大值还要大，target值一定不再这个row里面，那么我们就增加row，去下一排的row里面找。如果target比row中的最大值要小，说明target会出现在这个row中，那么我们就缩减col，然后一个一个找就行了。无fuck说

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or len(matrix) < 1 or len(matrix[0]) < 1:
            return False
        
        row, col = 0, len(matrix[0]) - 1
        while col >= 0 and row <= len(matrix) - 1:
            if target == matrix[row][col]:
                return True
            if target < matrix[row][col]:
                col -= 1
            else:
                row += 1
        return False

33. Search in Rotated Sorted Array

类型：考虑边界
Time Complexity O(logN)
Time Spent on this question: 50 mins

取中间值以后会发现，左边或者右边，至少有一边是sorted的，根据这个特性，搭配下面这个神图，就能理解下一段的代码

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return -1
        l , r = 0, len(nums) - 1
        
        while l <= r:
            mid = l + (r-l)//2
            if target == nums[mid]:
                return mid
            if nums[mid] >= nums[l]:
                if nums[l] <= target <= nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] <= target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

图片来源

81. Search in Rotated Sorted Array II

类型：考虑边界
Time Complexity O(logN)
Time Spent on this question: 10 mins

这道Followup 要处理一个边界，就是在最右边的数和最左边的数相等的时候，因为这可能会打乱左边Sorted的顺序
例如下面这个Edge Case

[1,3,1,1,1]
3

左边理论上来说不应该是sorted的，但是因为有最左边多出来的1的存在，导致了第一次会往左边，然后因为 nums[l] <= target <= nums[mid] 在这个情况下不成立，因为 1< 3 但是 3不小于1， 所以这里left = mid + 1后，跳过了3而找不到解，所以我们要做的是，解决这个最左边等于最右边的Edge Case

第一种方法:

if nums[l] == nums[mid] == nums[r]:
    l += 1
    r -= 1

第二种写法(参考caikehe)

while l < mid and nums[l] == nums[mid]:  l += 1

以下代码结合了第二种写法。

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        l , r = 0, len(nums) - 1
        while l <= r:
            mid = r - (r-l)//2
            if nums[mid] == target:
                return True
            #这里为了去掉左边多余出来的和右边重复的数，这种数会打乱Sorted的顺序。
            while l < mid and nums[l] == nums[mid]:
                l += 1
            #Left Side Sorted
            if nums[mid] >= nums[l]:
                if nums[l] <= target <= nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            #Right Side Sorted
            else:
                if nums[mid] <= target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return False