LeetCode 69. Sqrt(x)

来源：cnblogs　　作者：flowingfog　　时间：2018/10/20 15:12:59　　对本文有异议

分析

难度易

来源

https://leetcode.com/problems/sqrtx/description/

题目

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.

解答

方法1

 1 package LeetCode;
 2 /*
 3 蛮力，Runtime: 63 ms, faster than 6.02% of Java online submissions for Sqrt(x).
 4  */
 5 public class L69_SqrtX {
 6     public int mySqrt(int x) {
 7         int res=0;
 8         int curSquare=0;//记录上一轮平方数，
 9         int nextSquare=0;
10         for(int i=0;i<=x/2;i++)
11         {
12             nextSquare=(i+1)*(i+1);
13             if(nextSquare>x||nextSquare<curSquare)//如果平方溢出，一定是大于x的
14                 break;
15             else{
16                 res++;
17                 curSquare=nextSquare;
18             }
19         }
20         return res;
21     }
22 
23     public static void main(String[] args){
24         L69_SqrtX l69=new L69_SqrtX();
25         System.out.println(l69.mySqrt(2147395600));
26     }
27 }

方法2 牛顿法

1 public int mySqrt (int x) {
2     if (x <= 1)
3         return x;
4     double assume = x / 2;
5     while (Math.abs(Math.pow(assume, 2) - x) >=1) {
6         assume = (assume + x/assume) / 2;//求当前值与除以x的结果的均值，故能不断接近平方根
7     }
8     return (int) Math.floor(assume);
9 }

方法3 //二分查找

 1 public int mySqrt (int x) {
 2     if (x <= 1)
 3         return x;
 4     int left=1,right=Integer.MAX_VALUE;
 5     int res=0;
 6     while(left<right){
 7         res=left+(right-left)/2;//防止溢出
 8         if(res>x/res){
 9             right=res;
10         }else{
11             left=res;
12         }
13         if(right-left<=1)
14             break;
15     }
16     return (left+right)/2;
17 }