本文最后更新于 2025-03-30T12:48:37+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4 输出:2 示例 2:
输入:x = 8 输出:2 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 2^31 - 1
|
题目思路
- 1、二分法,还有一个叫做牛顿迭代法跟红蓝法,没研究,后面研究研究
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public: int mySqrt(int x) { long long l = 0, r = x; while(l < r) { long long mid = (l + r + 1) >> 1; if(mid <= x /mid) l = mid; else r = mid - 1; } return l; } };
|
复杂度
时间复杂度:O(logn)
空间复杂度:O(1)
Day 37 69. Sqrt(x)
https://chaggle.github.io/2021/10/16/Leetcode/91-day/day-37/