LeetCode - 69. Sqrt(x)

发布时间：2020-12-14 02:08:02 所属栏目：Linux 来源：网络整理

导读：Implement? int sqrt(int x) . Compute and return the square root of? x ,where? x ?is guaranteed to be a non-negative integer. Since the return type?is an integer,the decimal digits are truncated and only the integer part of the result?is re

Implement?int sqrt(int x).

Compute and return the square root of?x,where?x?is guaranteed to be a non-negative integer.

Since the return type?is an integer,the decimal digits are truncated and only the integer part of the result?is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842...,and since 
?            the decimal part is truncated,2 is returned.


使用暴力的方法 迭代，时间复杂度为O(n)
使用二分的方法，时间复杂度为O(logn)

 1 public int mySqrt(int x) {//二分 mytip
 2         if(0==x||1==x)
 3             return x;
 4         int left = 0;
 5         int right =x;
 6         while(left<=right){
 7             int mid = left+(right-left)/2;//可以使用(left+right)/2，但left或right过大时可能溢出
 8             int y = x/mid;//mid*mid越界
 9             if(mid<=y){
10                 int y1= x/(mid+1);
11                 if(y==mid||(mid+1)>y1){
12                     left =mid;
13                     break;
14                 }
15                 left=mid+1;
16             }
17             else{
18                 right=mid-1;
19             }
20         }
21         return left;
22     }

使用牛顿迭代法?https://blog.csdn.net/ccnt_2012/article/details/81837154

x_n+1 = x_n-f(x_n)/f‘(x_n) = x_n-(x²-y₀)/(2*x_n)=(x_n+y₀/x_n)/2

 1 public int mySqrt(int x) {//牛顿迭代法 mytip
 2         if(0==x||1==x){
 3             return x;
 4         }
 5         long r=x;
 6         while(r>x/r){
 7             r = (r+x/r)/2;
 8         }
 9         return (int)r;
10     }

相关题

有效的完全平方数 LeetCode367?https://www.cnblogs.com/zhacai/p/10631678.html?

扩展

根据精确度，返回double类型的结果

public double mySqrt1(double x,double pre) {
        double left = 0;
        double right =x;
        while((right-left)>pre){
            double mid = left+(right-left)/2;//可以使用(left+right)/2，但left或right过大时可能溢出
            double y = x/mid;//mid*mid越界
            if(y ==mid){
                left=mid;
                right = mid;
                break;
            }
            else if(y>mid){
                left=mid;
            }
            else{
                right=mid;
            }
        }
        //System.out.println(left);
        //System.out.println((left+right)/2);
        return left+(right-left)/2;
    }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!