当前位置:网站首页>【LeetCode-69】x的平方根
【LeetCode-69】x的平方根
2022-08-11 05:30:00 【Ring*】
10.2 x的平方根【69】
10.2.1 题目描述
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
10.2.2 方法一:袖珍计算器算法
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
int ans = (int) Math.exp(0.5 * Math.log(x));
return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}
}
复杂度分析
- 时间复杂度:O(1),由于内置的 exp 函数与 log 函数一般都很快,我们在这里将其复杂度视为 O(1)。
- 空间复杂度:O(1)。
10.2.3 方法二:二分查找
class Solution {
public int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
复杂度分析
- 时间复杂度:O(log x),即为二分查找需要的次数。
- 空间复杂度:O(1)。
10.2.4 my answer—二分查找
class Solution {
public int mySqrt(int x) {
int left = 0;
int right = x;
int ans = -1;
while (left<=right){
int mid = (left+right)/2;
if((long)mid*mid<=x){
ans = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return ans;
}
}
边栏推荐
猜你喜欢
随机推荐
Js method commonly used objects and attributes
Byte (byte) and bit (bit)
【无标题】
Tinker的自我介绍
Promise.race learning (judging the fastest execution of multiple promise objects)
The whole process of Tinker access --- Compilation
Day 85
星盟-pwn-babyfmt
JNI入门
JS案例练习(pink老师经典案例)
厂商推送平台-华为接入
swagger常用注释API @ApiModel、@ApiModelProperty的用法
C语言预处理
The Summer of Open Source 2022 is coming | Welcome to sign up for the OpenMLDB community project~
编译异常解决
USB in NRZI to encode the data
The role of the port
js 学习进阶(Dom部分 pink老师教学笔记)
使用adb命令管理应用
本地服务配置内网穿透实现微信公众号整合