跳至主要內容

0374. 猜数字大小

ITCharge大约 2 分钟

0374. 猜数字大小open in new window

  • 标签:二分查找、交互
  • 难度:简单

题目链接

题目大意

描述:猜数字游戏。给定一个整数 nn 和一个接口 def guess(num: int) -> int:,题目会从 1n1 \sim n 中随机选取一个数 xx。我们只能通过调用接口来判断自己猜测的数是否正确。

要求:要求返回题目选取的数字 xx

说明

  • def guess(num: int) -> int: 返回值:
    • 1-1:我选出的数字比你猜的数字小,即 pick<numpick < num
    • 11:我选出的数字比你猜的数字大 pick>numpick > num
    • 00:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick==numpick == num

示例

  • 示例 1:
输入:n = 10, pick = 6
输出:6
  • 示例 2:
输入:n = 1, pick = 1
输出:1

解题思路

思路 1:二分查找

利用两个指针 leftleftrightrightleftleft 指向数字 11rightright 指向数字 nn。每次从中间开始调用接口猜测是否正确。

  • 如果猜测的数比选中的数大,则将 rightright 向左移,令 right = mid - 1,继续从中间调用接口猜测;
  • 如果猜测的数比选中的数小,则将 leftleft 向右移,令 left = mid + 1,继续从中间调用的接口猜测;
  • 如果猜测正确,则直接返回该数。

思路 1:二分查找代码

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n
        while left <= right:
            mid = left + (right - left) // 2
            ans = guess(mid)
            if ans == 1:
                left = mid + 1
            elif ans == -1:
                right = mid - 1
            else:
                return mid
        return 0

思路 1:复杂度分析

  • 时间复杂度O(logn)O(\log n)。二分查找算法的时间复杂度为 O(logn)O(\log n)
  • 空间复杂度O(1)O(1)。只用到了常数空间存放若干变量。