374. 猜数字大小
374. 猜数字大小
题目
We are playing the Guess Game. The game is as follows:
I pick a number from 1
to n
. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num)
, which returns three possible results:
-1
: Your guess is higher than the number I picked (i.e.num > pick
).1
: Your guess is lower than the number I picked (i.e.num < pick
).0
: your guess is equal to the number I picked (i.e.num == pick
).
Return the number that I picked.
Example 1:
Input: n = 10, pick = 6
Output: 6
Example 2:
Input: n = 1, pick = 1
Output: 1
Example 3:
Input: n = 2, pick = 1
Output: 1
Constraints:
1 <= n <= 2^31 - 1
1 <= pick <= n
题目大意
猜数字游戏的规则如下:
- 每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num)
来获取猜测结果,返回值一共有 3 种可能的情况(-1
,1
或 0
):
-1
:我选出的数字比你猜的数字小pick < num
1
:我选出的数字比你猜的数字大pick > num
0
:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num
返回我选出的数字。
解题思路
可以采用二分查找解决。
复杂度分析
- 时间复杂度:
O(logn)
,二分查找的时间复杂度是O(logn)
。 - 空间复杂度:
O(1)
。
代码
/**
* @param {number} n
* @return {number}
*/
var guessNumber = function (n) {
let left = 1;
let right = n;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (guess(mid) == 0) {
return mid;
} else if (guess(mid) == 1) {
left = mid + 1;
} else if (guess(mid) == -1) {
right = mid - 1;
}
}
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
278 | 第一个错误的版本 | [✓] | 二分查找 交互 | |
375 | 猜数字大小 II | [✓] | 数学 动态规划 博弈 | |
658 | 找到 K 个最接近的元素 | 数组 双指针 二分查找 3+ |