网络异常,图片无法展示
|
题目地址(374. 猜数字大小)
题目描述
猜数字游戏的规则如下: 每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0): -1:我选出的数字比你猜的数字小 pick < num 1:我选出的数字比你猜的数字大 pick > num 0:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num 返回我选出的数字。 示例 1: 输入:n = 10, pick = 6 输出:6 示例 2: 输入:n = 1, pick = 1 输出:1 示例 3: 输入:n = 2, pick = 1 输出:1 示例 4: 输入:n = 2, pick = 2 输出:2 提示: 1 <= n <= 231 - 1 1 <= pick <= n
思路
二分法实现
代码
- 语言支持:Python3
Python3 Code:
# The guess API is already defined for you. # @param num, your guess # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 # def guess(num: int) -> int: class Solution: def guessNumber(self, n: int) -> int: left, right = 0, n while left <= right: mid = (left + right)//2 res = guess(mid) if res == 0: return mid elif res == -1: right = mid - 1 else: left = mid + 1 return -1
复杂度分析
令 n 为数组长度。
- 时间复杂度:O(logn)O(logn)
- 空间复杂度:O(1)O(1)