leetcode-求x的开平方

LeetCode

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

1
2
3
> 输入: 4
> 输出: 2
>

示例 2:

1
2
3
4
5
> 输入: 8
> 输出: 2
> 说明: 8 的平方根是 2.82842..., 
>      由于返回类型是整数，小数部分将被舍去。
>

代码实现

Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int mySqrt(int x) {
        int left = 1;
        int right = x / 2;
        while (left <= right) {
            int mid = (left + right) / 2;
            int result = x / mid;
            if (result == mid) {
                return mid;
            }
            if (result < mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return x / left < left ? left - 1 : left;
    }
}
Python实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 1
        r = x
        while l <= r:
            mid = int((l + r) / 2)
            if mid * mid == x:
                return mid
            elif mid * mid < x:
                l = mid + 1
            elif mid * mid > x:
                r = mid - 1
        if l * l > x:
            return l - 1
        return l

不同语言实现算法的注意点

该问题，如果采用Python来实现的话，是不出现整数溢出的情况的，这里我直接给出一个测试用例，其中mid * mid的结果为1152826965724840000

x = 2147395599

而如果采用Java语言去实现Python的该题解算法，会发现，当x变大时，结果基本是不正确的，进过调试才发现，由于采用mid * mid的方法去计算，极容易出现整数溢出的情况，导致进入错误的分支语句