Day 1 数组 二分：35.搜索插入, 34. 排序数组第一和最后, 69. 平方根, LC 367. 有效完全平方数

LC 35.搜索插入位置

  • 思路
    • example: [1,3,5], target = 0,1,2,3,4,5,6
      • nums = [5], target = 5, ans = 0
      • nums = [5], target = 6, ans = 1
      • nums = [5], target = 4, ans = 0
    • 已排好序，无重复元素
    • 类似 “插入位置：第1个>=target的位置”，答案范围：0,1,..., n
    • 二分模板2，左闭右开, left = 0, right = n (NOT n-1), while left < right, <, >=; quit when left == right
  • 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n
        while left < right: # [left, right)
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else: # nums[mid] >= target
                right = mid
        return left # or right
  • 用左闭右闭思路更好理解。
    • [left, right]表示答案的存在范围，初始left = 0, right = n。
    • mid是向下取整的“一半”
    • nums[mid] < target：插入位置必在[mid+1, right] （左半部不可能包含答案）
    • nums[mid] >= target: 插入位置必在[left, mid], 注意mid仍有可能是答案 （mid右边不可能包含答案）
    • 终止条件：left == right, 这个时候mid = left = right, 如果nums[mid] >= target，指针不会有变化，死循环。所以left == right时就停止。
      • 最后left == right是由3个元素或2个元素变为1个元素。
        －最后return left (或 right)
  • 左闭右闭 (用这个版本，可拓展）
    • 类似 “插入位置：第1个>=target的位置”，答案范围：0,1,..., n
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid 
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left  # left \in [0,...,n]
  • 下面的版本可针对有重复元素的情况。更一般。
    • bisect_left
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n-1 
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left # could be n

34. 排序数组中查找第一个和最后一个位置

  • 思路
    • example
    • 已排好序，有重复元素
    • 第1个==位置，最后一个==位置
    • 二分模板1，左闭右闭, left = 0, right = n-1, while left <= right, ==, >, <; quit when left > right
      • type = 'first' or 'last'
    • type = 'first'
      • nums[mid] > target: 答案在[left, mid-1]
      • nums[mid] < target: 答案在[mid+1, right]
      • nums[mid] == target: 答案在[left, mid], 但是第一个等于target的位置可能在更左边。 为方便，直接去[left, mid-1]找可能的答案。
      • while left <= right:
      • 最后一步left==right时，判断最可能的答案 （可能越界：n)（return left)。
    • type = 'last'
      • nums[mid] > target: 答案在[left, mid-1]
      • nums[mid] < target: 答案在[mid+1, right]
      • nums[mid] == target: 答案在[left, mid], 但是最后一个等于target的位置可能在更右边。 为方便，直接去[mid+1, right]找可能的答案。
      • while left <= right:
      • 最后一步left==right时，判断最可能的答案 （可能越界：-1)（return right)。
  • 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        def BinarySearch(left, right, type):
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target and type == 'first':
                    right = mid - 1
                elif nums[mid] > target: # both cases
                    right = mid - 1
                else: # 'first': < target; 'last': <= target
                    left = mid + 1
            return left if type == 'first' else right 
        idx1 = BinarySearch(0, n-1, 'first')
        idx2 = BinarySearch(0, n-1, 'last')
        if idx1 > idx2: return [-1, -1]
        return [idx1, idx2]
  • 另一个思路：
    • 数组前面加-\infty,后面加\infty.
    • 第一个 >=target 位置: idx1；答案在[0,...,n]中; 左闭右闭二分模板2：while left < right。
    • 第一个 >target 位置: idx2，答案在[0,...,n]中; 左闭右闭二分模板2：while left < right。
    • 注意要判断idx1是否等于n或者对应数字是否等于target。
    • idx2 -= 1得到最后一个<= target 位置。
    • mid = left + (right - left) // 2,向下取整（可能等于left)，所以二分写法如果出现left = mid,可能会死循环。
  • 用这个版本
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch_first(nums, target): # search the first position >= target 
            n = len(nums)
            left, right = 0, n-1 
            while left <= right: 
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1 
                else: # nums[mid] == target 
                    right = mid - 1
            # now left > right, left in [0,...,n]
            return left 
        def binarySearch_last(nums, target): # search the last position >= target 
            n = len(nums)
            left, right = 0, n-1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target: 
                    right = mid - 1
                else: # == 
                    left = mid + 1
            # now right > left, right in [-1,0,...,n-1]
            return right 
        idx1 = binarySearch_first(nums, target)
        if idx1 == n or nums[idx1] != target:
            return [-1, -1]
        idx2 = binarySearch_last(nums, target) 
        return [idx1, idx2]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch_first(nums, target): # 1st index, >= target
            n = len(nums)
            left, right = 0, n-1 
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] >= target:
                    right = mid -1 
            return left  
        def binarySearch_last(nums, target): # last index, >= target 
            n = len(nums)
            left, right = 0, n-1 
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] <= target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid -1 
            return right  
        n = len(nums)
        idx1 = binarySearch_first(nums, target) 
        if idx1 == n or nums[idx1] != target: 
            return [-1, -1] 
        idx2 = binarySearch_last(nums, target) 
        return [idx1, idx2]

LC 69: 平方根

  • 思路
    • example
    • largest k such that k*k <= x
    • 二分模板1，左闭右闭, <=, >
  • 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        res = 0
        while left <= right:
            mid = left + (right - left) // 2
            num = mid * mid
            if num <= x:
                res = mid
                left = mid + 1
            else: # num > x
                right = mid - 1
        return res
  • 这个版本也可以
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x 
        while left <= right:
            mid = left + (right - left) // 2
            mid2 = mid * mid 
            if mid2 == x:
                return mid 
            elif mid2 < x:
                left = mid + 1
            else: # mid2 > x 
                right = mid - 1
        return right

LC 367. 有效完全平方数

  • 思路
    • example
    • find k such that k*k == num
    • 二分模板1，左闭右闭, ==, <, >
  • 复杂度. 时间：O(log n), 空间: O(1)
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 0, num
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid
            if square == num:
                return True
            elif square < num:
                left = mid + 1
            else:
                right = mid - 1
        return False
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容