69, x的平方根
2023/9/30大约 3 分钟
一、题目描述
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入: x = 4
输出: 2
解释: 4的平方根是2,所以返回2.
示例 2:
输入: x = 8
输出: 2
解释: 8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
- 0 <= x <= 2³¹ - 1
相关主题:
- 数学
- 二分查找
二、题解
方法 1: 二分查找
Rust
pub fn my_sqrt(x: i32) -> i32 {
//Self::left_close_right_open(x)
Self::left_close_right_close(x)
}
pub fn left_close_right_open(x: i32) -> i32 {
let x = x as i64;
let (mut left, mut right) = (0_i64, x + 1);
while left < right {
let mid = left + (right - left) / 2;
let square = mid * mid;
if square > x {
right = mid;
} else if square < x {
left = mid + 1;
} else {
return mid as i32;
}
}
left as i32 - 1
}
pub fn left_close_right_close(x: i32) -> i32 {
let x = x as i64;
let (mut left, mut right) = (0_i64, x);
while left <= right {
let mid = left + (right - left) / 2;
let square = mid * mid;
if square > x {
right = mid - 1;
} else if square < x {
left = mid + 1;
} else {
return mid as i32;
}
}
left as i32 - 1
}
Java
public int mySqrt(int x) {
//return this.leftCloseRightOpen(x);
return this.leftCloseRightClose(x);
}
public int leftCloseRightOpen(int x) {
long len = (long)x;
long left = 0;
long right = len + 1; // 左闭右开,right需要为len+1
while (left < right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square > len) {
right = mid;
} else if (square < len) {
left = mid + 1;
} else {
return (int) mid;
}
}
return (int) (left - 1);
}
public int leftCloseRightClose(int x) {
long len = (long)x;
long left = 0;
long right = len;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square > len) {
right = mid - 1;
} else if (square < len) {
left = mid + 1;
} else {
return (int)mid;
}
}
return (int)left - 1;
}
Go
func mySqrt(x int) int {
//return leftCloseRightOpen(x)
return leftCloseRightClose(x)
}
func leftCloseRightOpen(x int) int {
var newX = int64(x)
left, right := int64(0), newX+1
for left < right {
mid := left + (right-left)/2
square := mid * mid
if square > newX {
right = mid
} else if square < newX {
left = mid + 1
} else {
return int(mid)
}
}
return int(left - 1)
}
func leftCloseRightClose(x int) int {
var newX = int64(x)
left, right := int64(0), newX
for left <= right {
mid := left + (right-left)/2
square := mid * mid
if square > newX {
right = mid - 1
} else if square < newX {
left = mid + 1
} else {
return int(mid)
}
}
return int(left - 1)
}
C#
public int MySqrt(int x)
{
//return LeftCloseRightOpen(x);
return LeftCloseRightClose(x);
}
int LeftCloseRightOpen(int x)
{
long newX = x;
(long left, long right) = (0, newX + 1);
while (left < right)
{
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square > newX)
right = mid;
else if (square < newX)
left = mid + 1;
else
return (int)mid;
}
return (int)left - 1;
}
int LeftCloseRightClose(int x)
{
long newX = x;
(long left, long right) = (0, newX);
while (left <= right)
{
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square > newX)
right = mid - 1;
else if (square < newX)
left = mid + 1;
else
return (int)mid;
}
return (int)left - 1;
}
C++
int mySqrt(int x) {
//return leftCloseRightOpen(x);
return leftCloseRightClose(x);
}
int leftCloseRightOpen(int x) {
const long new_x = x;
auto[left, right] = std::make_pair(0, new_x + 1);
while (left < right) {
const auto mid = left + (right - left) / 2;
const auto square = mid * mid;
if (square > new_x)
right = mid;
else if (square < new_x)
left = mid + 1;
else
return mid;
}
return left - 1;
}
int leftCloseRightClose(int x) {
const long new_x = x;
auto[left, right] = std::make_pair(0, new_x);
while (left <= right) {
const auto mid = left + (right - left) / 2;
const auto square = mid * mid;
if (square > new_x)
right = mid - 1;
else if (square < new_x)
left = mid + 1;
else
return mid;
}
return left - 1;
}