首页 > 试题广场 >

求平方根

[编程题]求平方根

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

实现函数 int sqrt(int x).

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

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

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

示例1

输入

输出

示例2

输入

2143195649

输出

算法知识视频讲解

Java

牛客839384289号

public int sqrt (int x) {
    // write code here
    long p1=0 ,p2=x;
    while(p1<=p2){
        long mid=(p1+p2)/2;
        if(mid*mid<=x && (mid+1)*(mid+1)>x){
            return (int)mid;
        }else if((mid*mid)>x){
            p2=mid;
        }else{
            p1=mid+1;
        }
    }
    return -1;
}

发表于 2024-05-26 13:57:39 回复(0)

Java

贾天龙

import java.util.*;


public class Solution {
    /**
     *
     * @param x int整型
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        if (x == 0 || x == 1) {
            return x;
        }


        int left = 2;
        int right = x;

        while (true) {
            int mid = left + ((right - left) >> 1);
            // 这里不用mid * mid > x，防止mid *mid 的结果太大，溢出
            if (mid > x/mid) {
                right = mid - 1;
            } else {
                // mid^2<=x  (mid+1)^2>x 所以mid就是那个值
                if(mid+1>x/(mid+1)){
                    return mid;
                }
                left = mid + 1;
            }
        }
    }
}

发表于 2023-03-03 21:25:27 回复(0)

Java

牛客191072895号

public class Solution {
    public int sqrt (int x) {
        if(x <= 1) return x;
        int left = 1;
        int right = x / 2;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(mid == x / mid){
                return mid;
            }else if(mid < (x / mid)){
                if((mid + 1) * (mid + 1) > x){
                    return mid;
                }else{
                    left = mid + 1;
                }
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

发表于 2022-06-29 21:59:18 回复(0)

Java

橘子不是唯一的水果yu

emm我知道我很菜

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        //return (int) Math.sqrt(x);
        for(int i = 0; i <= x; i++){
            if(i * i > x){
                return i - 1;
            }
            if(i * i == x){
                return i;
            }
        }
        return 0;
    }
}

编辑于 2021-12-13 15:19:03 回复(1)

Java

FARO_Z

主要考察小细节：
1、直接相乘会导致溢出
2、什么地方该加一，什么地方不该加一

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        if (x<=1) return x;
        int l=0,r=x;
        while (l<=r) {
            int mid = (l + r) / 2;
            if (mid<=x/mid && (mid+1)>x/(mid+1)) return mid;
            if (mid>x/mid) r=mid-1;
            else l=mid+1;
        }
        return -1;
    }
}

发表于 2021-11-26 16:58:08 回复(1)

Java

Carmen-Xiao

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        if(x==0) return 0;
        int left=1,right=x;
//         while(left<=right){
        while(true){
            int mid=left+(right-left)/2;
            if(mid>x/mid){
                right=mid-1;
            }else{
                if((mid+1)>x/(mid+1)) return mid;
                left=mid+1;
            }
        }
    }
}

发表于 2021-11-21 20:06:31 回复(0)

Java

mutex_

// 我写的什么玩意

public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        if(x<=1) return x;
        int mid=x/2;
        int high=0, low=0;
        while(mid>0){
            // 不能写成mid*mid>x 因为会越界
            if(mid>x/mid){
                mid=mid/2;
            }else if(mid < x/mid){  
                low=mid;
                high=mid*2;
                break;
            }else{
                return mid;
            }
        }
        //System.out.println("high:"+high);
        //System.out.println("low:"+low);

        for(int i=high; i>=low;i--){
            if(i>x/i){
                continue;
            }else{
                return i;
            }
        }
        return -1;  
    }
}

发表于 2021-11-16 20:53:27 回复(0)

Java

LDew

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        double l = 0,r = x;
        while(r - l > 0.00001){
            double mid = (l + r) / 2;
            if(mid * mid > x)r = mid;
            else l = mid;
        }
        return (int)r;
    }
}

发表于 2021-11-08 17:40:27 回复(0)

Java

Vtech

数据范围： 0 < x < 2^{31}0<x<231

用例输入 0

？？？？？？？？

发表于 2021-10-19 10:32:43 回复(0)

Java

白色黄昏

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        long ans = 0L;
        long L = 1L;
        long R = x;
        while (L <= R) {
            long M = L + ((R - L) >> 1);
            if (M * M <= x) {
                ans = M;
                L = M + 1;
            } else {
                R = M - 1;
            }
        }
        return (int) ans;
    }
}

发表于 2021-10-05 13:14:43 回复(0)

Java

刻苦的大熊猫在度假

java

public int sqrt (int x) {
        // write code here
        int ans = 0;
        int i;
        for(i=1;i*i<=x;i++);
        ans = i-1;
        return ans;
    }

发表于 2021-10-04 16:35:23 回复(0)

Java

牛客774608432号

public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        int l = 1;
        int r = x;
        while (l <= r) {
            int mid = l + r >>> 1;
            if (mid > x / mid) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}

发表于 2021-10-04 12:34:19 回复(0)

Java

QinGL_ZYW

二分法

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        int l = 0, r = x;
        while(l <= r){
            int mid = (l+r) >> 1;
            long tem = (long)mid * mid;
            if(tem > x){
                r = mid - 1;
            }else if(tem < x){
                l = mid + 1;
            }else{
                return mid;
            }
        }
        return r;
    }
}

发表于 2021-10-03 20:33:03 回复(0)

Java

千叶牧屿

    public int sqrt (int x) {
        boolean flag = false;
        Long temp = Long.parseLong(Integer.toString(x));
        Long dep = 0L;
        while(!flag){
          if(temp*temp <= x && (temp+1)*(temp+1)>x){
              flag = true;
          }else if(temp*temp > x) {
              dep = temp;
              temp=temp/2;
          }else if(temp*temp < x) {
              temp = (dep + temp) / 2;
          }
        }
        return Integer.parseInt(temp.toString());
    }

发表于 2021-09-30 14:34:10 回复(0)

Java

牛客55610971号

思路：

1 首先确定平方根的位数为：x的位数%2==0?x的位数/2:x的位数/2+1。

2 然后采用二分法，进行求解

import java.util.*;

public class Solution {
/**
*
* @param x int整型
* @return int整型
*/
public int sqrt (int x) {
// write code here
if(x==0) return 0;
int parentlen = Integer.toUnsignedString(x).length();
int sonlen = parentlen%2==0?parentlen/2:parentlen/2+1;
//System.out.println("--------sonlen------"+sonlen);
int start = 1;

for(int i=sonlen;i>1;i--){
start = start * 10 ;
}
//System.out.println("--------start------"+start);
int end = start*10-1;
//System.out.println("--------end------"+end);
return recursionBinarySearch((long)x,start,end);
}

public static int recursionBinarySearch(long key,int low,int high){
        if(low==high)
        {
            return low;
        }
        if(key < (long)low*low||key>(long)(high+1)*(high+1)||low > high){
            return -1;
        }

        int middle = (low + high) / 2;            //初始中间位置
        if((long)middle*middle > key&&(long)(middle+1)*(middle+1) > key){
            //比关键字大则关键字在左区域
            return recursionBinarySearch( key, low, middle - 1);
        }else if((long)middle*middle < key&&(long)(middle+1)*(middle+1) < key){
            //比关键字小则关键字在右区域
            return recursionBinarySearch( key, middle + 1, high);
        }else if((long)middle*middle <= key&&(long)(middle+1)*(middle+1) > key){
            return middle;
        }else if((long)(middle+1)*(middle+1) == key){
            return middle+1;
        }
        return -1;
    }
}

发表于 2021-09-14 15:04:05 回复(0)

Java

se-rye

二分法

public class Solution {
    public int sqrt (int n) {
        int i = 0;
        int j = n;
        while (i <= j) {
            long mid = (i + j) / 2; // 防止溢出
            if (mid * mid == n || (mid * mid < n && (mid + 1) * (mid + 1) > n)) {
                return (int)mid;
            } else if (mid * mid > n) {
                j = (int)(mid - 1);
            } else {
                i = (int)(mid + 1);
            }
        }
        return -1; // n的平方根不存在
    }
}

发表于 2021-09-12 17:47:41 回复(0)