练习题

1.1在排序数组中查找元素的第一个和最后一个位置 (opens new window)

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为

O(log n) 的算法解决此问题。

">

笔记

二分+双指针

::

class Solution:
  """
  先用二分查找找到第一个出现得位置，然后找出左右边界
  """
  def searchRange(self, nums: List[int], target: int) -> List[int]:

      left, right = 0, len(nums) -1  # left 代表最左边，right最右边
      while left <= right:
          mid = (left+right)//2
          if nums[mid]== target:
              left = right = mid
              while left>=0 and nums[left] == target:
                  left -=1
              while right <= len(nums)-1 and nums[right] == target:
                  right += 1 
              return [left+1, right-1]
          elif nums[mid] > target:
              right = mid -1
          else:
              left = mid +1
          
      return [-1, -1]

笔记

方法二： 二分+分别寻找左右边界

class Solution:
  def searchRange(self, nums: List[int], target: int) -> List[int]:

      def searchleft(nums: List[int], target:int):
          
          left, right = 0, len(nums) -1

          while left <= right:

              mid = (left + right)//2

              if nums[mid] == target:
                  right -= 1
              elif nums[mid] > target:
                  right = mid -1

              else:
                  left = mid + 1
          return left if nums[left] == target else -1

      def searchright(nums:List[int], target: int):

          left, right = 0, len(nums) -1
          while left <= right:

              mid = (left + right)//2

              if nums[mid] == target:
                  left += 1
              elif nums[mid] > target:
                  right = mid -1

              else:
                  left = mid + 1
          return right if nums[right]== target else -1
      if not nums or nums[0]> target or nums[len(nums)-1] <target:
          return [-1, -1]
      left, right = searchleft(nums, target), searchright(nums, target)
      return [left, right]

// Make sure to add code blocks to your code group

1.2. 搜索旋转排序数组 (opens new window)

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

class Solution:
  def search(self, nums: List[int], target: int) -> int:

      left, right = 0, len(nums) -1
      
      while left <=right:
          mid = (left + right)//2
          #有序部分
          if nums[mid] == target:
              return mid

          if nums[0] <= nums[mid]:  # 再递减序列里
              if nums[0]<=target< nums[mid]:  
                  right = mid -1
              else:
                  left = mid +1

          else: #  一半升序，一半降序，前半部分>后半部分

              if nums[mid] < target<=nums[len(nums) -1]:
                  left = mid +1
              else:
                  right = mid - 1
      return -1

// Make sure to add code blocks to your code group

1.3. 山脉数组的峰顶索引 (opens new window)

符合下列属性的数组 arr 称为 山脉数组 ： arr.length >= 3 存在 i（0 < i < arr.length - 1）使得： arr[0] < arr[1] < ... arr[i-1] < arr[i] arr[i] > arr[i+1] > ... > arr[arr.length - 1] 给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

class Solution:
  def peakIndexInMountainArray(self, arr: List[int]) -> int:

      left, right = 0, len(arr) -1

      while left < right:
          mid = (left + right) //2

          if arr[mid] > arr[mid+1] and arr[mid-1] < arr[mid]:
              return mid
          elif arr[mid] < arr[mid+1]:
              left = mid
          else:
              right = mid

// Make sure to add code blocks to your code group

1.4. 寻找峰值 (opens new window)

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

class Solution:
  """
  target = nums[mid-1]<numd[mid]> nums[mid+1]
  """
  def findPeakElement(self, nums: List[int]) -> int:
      
      left, right = 0, len(nums)-1

      while left+1<=right:
          mid = (left +right)//2
          if nums[mid] > nums[mid+1]:
              right = mid
          else:
              left = mid +1
      return (left +right)//2

// Make sure to add code blocks to your code group

1.5. 第一个错误的版本 (opens new window)

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
  def firstBadVersion(self, n: int) -> int:
      left, right = 1, n

      while left<right:
          
          mid = (left + right)//2

          tag1 = isBadVersion(mid)
          if tag1:
              right = mid
          else:
              left = mid +1
          
      return right

// Make sure to add code blocks to your code group

6. 搜索二维矩阵 (opens new window)

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

class Solution:
  def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:


      m = len(matrix) -1
      n = len(matrix[0]) -1

      # TODO 先用二分查找判断在哪一行
      top, buttom = 0, m
      possible_row = -1
      while top<=buttom:
          mid = (top+buttom)// 2

          if matrix[mid][0]>target:
              buttom = mid -1
          elif matrix[mid][n]<target:
              top = mid+1
          elif matrix[mid][0] <=target <= matrix[mid][n]:
              if matrix[mid][0] == target or matrix[mid][n] == target:
                  return True
              possible_row = mid
              break
      # 没有找到合适的区间行，返回false
      if possible_row == -1:
          return False
      # TODO 用二分查找是否是在这一行里
      left, right = 0, n
      row = matrix[possible_row]
      while left <= right:

          mid = (left +right)//2

          if row[mid] == target:
              return True

          elif row[mid] > target:
              right =mid-1
          else:
              left = mid +1
      return False

// Make sure to add code blocks to your code group

1.7. 搜索二维矩阵 II (opens new window)

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

// Make sure to add code blocks to your code group

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        m = len(matrix)-1
        n = len(matrix[0])-1
        
        # 每一行中进行二分查找
        for i in range(m+1):

            row = matrix[i]

            left, right = 0, n

            while left <= right:
                mid = (left + right)//2

                if row[mid] == target:
                    return True
                elif row[mid] < target:
                    left = mid +1
                else:
                    right = mid -1
        return False

1.8. x 的平方根 (opens new window)

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

// Make sure to add code blocks to your code group

class Solution:
    def mySqrt(self, x: int) -> int:

        # x：为正整数   求数平方根 结果向下取整

        left, right = 0, x
        
        while left <=right:
            mid = (left + right)//2
            if (mid+1) * (mid+1) > x and mid * mid <= x :
                return mid
            elif mid * mid < x:
                left = mid +1
            else:
                right = mid -1

1.9. 有序数组中的单一元素 (opens new window)

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

class Solution:

  """

  当 \textit{mid}mid 是偶数时，mid + 1 = mid^1；

  当 \textit{mid}mid 是奇数时，mid - 1 = mid^1。
  """
  def singleNonDuplicate(self, nums: List[int]) -> int:
      low, high = 0, len(nums) - 1
      while low < high:
          mid = (low + high) // 2
          if nums[mid] == nums[mid ^ 1]:
              low = mid + 1
          else:
              high = mid
      return nums[low]

// Make sure to add code blocks to your code group

1.10. 按权重随机选择 (opens new window)

给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

// Make sure to add code blocks to your code group