求平方根

[编程题]求平方根

热度指数：158010 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现函数 int mysqrt(int x).

计算并返回 x 的平方根（向下取整）

数据范围： $0 <= x < 2^{31}-1$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(logx)$

示例1

输入

输出

示例2

输入

2143195649

输出

算法知识视频讲解

查看答案及解析

五条梧

int mysqrt(int x ) {

// write code here

if (x <= 1)

{

return x;

}

int left = 0, right = x;

while (left < right)

{

int mid = left + (right - left) / 2;

if (x / mid >= mid)

{

left = mid + 1;

}

else

{

right = mid;

}

return right - 1;

}

发表于 2023-10-27 16:51:37 回复(0)

80后大叔

二分法

class Solution {
  public:
    /**
     *
     * @param x int整型
     * @return int整型
     */
    int mysqrt(int x) {
        if(x==1) return 1;
        if(x==0) return 0;
        int left = 0; // 左边界
        int right = x; // 右边界
        while(left <= right) {
            int mid = left + (right-left)/2; // 防止int溢出，等同于(left+right)/2
            if(mid==x/mid || (mid<x/mid && (mid+1)>x/(mid+1))) return mid;
            if(mid<x/mid) left=mid+1;
            if(mid>x/mid) right=mid-1;
        }
        return -1;
    }
};

发表于 2022-11-08 11:44:47 回复(0)

病入膏肓的中二Z战士

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param x int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int Sqrt(int x ) {
    // write code her
    return mysqrt(x)/1;
}就是懒~~~  佬勿喷

发表于 2022-02-09 19:18:49 回复(0)