leetcode 69. 实现Sqrt(x)

系统管理员 2023-06-21 10:27 12阅读 0赞

[https://leetcode.com/problems/sqrtx/][https_leetcode.com_problems_sqrtx]

计算并返回一个整数x的平方根，x保证是非负整数

## 一、题目分析 ##

## 题目给了两个测试用例 ##

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

可见，题目只是要求返回一个整数，如果一个整数的平方根有小数部分，那么需要把小数部分截取掉，只返回整数部分。由于一个数 x 的开方 sqrt 一定在 0 - x 之间，并且满足 sqrt == x / sqrt。因此，我们可以利用二分查找在 0 ~ x 之间查找 最后一个sqrt，使得sqrt \* sqrt == x。

## 二、代码实现 ##

class Solution {
        public int mySqrt(int x) {  //x >= 0
            if (x == 0 || x == 1) {
                return x;
            }
            
            int left = 1, right = x;
            
            while (left < right) {
                //注意这里不能使用mid := floor( (left+right) /2 )，否则会死循环
                //int mid = (right - left) / 2 + left;
                //
                //mid := ceil( (left+right) /2 )
                int mid = right - (right - left) / 2;
                
                //注意这里要强转为long，否则会溢出
                if ((long)mid * mid <= (long)x) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            
            //left == right
            //当循环结束，left就是最后一个平方小于等于x的整数了
            return left;
        }   
    }

更好的实现方式：

由于平方根是整数，这时相当于不重复的二分查找的情况

public int mySqrt(int x) {   
        if (x <= 1) {
            return x;
        }
        
        int left = 1, right = x;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //这里与上面的实现方式相比，由于采用除法，不会有溢出的危险
            int sqrt = x / mid;
    
            if (sqrt == mid) {
                return mid;
            } else if (mid > sqrt) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    
        //left > right，并且left和right相差1，所以对于平方根带有小数的x，返回的是right
        return right;
    }

[https_leetcode.com_problems_sqrtx]: https://leetcode.com/problems/sqrtx/