首页 > 代码库 > [leetcode] Sqrt(x)

[leetcode] Sqrt(x)

2024-07-09 23:43:50   223人阅读

Implement int sqrt(int x).

Compute and return the square root of x.

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

 

思路1：一个数的平方根肯定在0~x/2+1之间，因此在这个范围内二分查找。

　　注意：

  • 　　中间结果用long，否则mid*mid溢出。
  • 　　对于搜索不到的情况（找的到其实也是），返回平方根的floor值。

思路2：牛顿迭代法。

 

public class Solution {    public int sqrt(int x) {        if (x < 0)            return -1;        long right = x / 2 + 1;        long left = 0;        long mid;        while (left <= right) {            mid = (left + right) / 2;            if (x < mid * mid)                right = mid - 1;            else if (x > mid * mid)                left = mid + 1;            else                return (int) mid;        }        return (int) right;    }    public static void main(String[] args) {         System.out.println(new Solution().sqrt(0));         System.out.println(new Solution().sqrt(1));         System.out.println(new Solution().sqrt(2));         System.out.println(new Solution().sqrt(3));         System.out.println(new Solution().sqrt(4));        System.out.println(new Solution().sqrt(2147483647));    }}
View Code

 

参考：

http://blog.csdn.net/linhuanmars/article/details/20089131

http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html

 

 


联系
我们