[leetcode题解]快速求解某数的下取整平方根

leetcode第69题,计算某数的下取整平方根sqrt(x)

题目如下:

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.

下取整平方根,意思就是计算某数的平方根,如果带有小数则直接取其整数部分,即向下取整。

解题思路就是使用二分法进行计算,如果m*m正好等于给定的x,则m即为解,如果m * m > x,那很显然,解在l到m-1之间,如果m * m < x,这个时候我们就需要判断(m+1)* (m+1)与x的关系,如果(m+1)* (m+1)也小于x,那么解就在m+1到r之间,否则m就是解,因为精确解一定是大于m小于m+1的,取整数后为m。


int mySqrt(int x) {
    if (0 == x)
        return x;
    
    int l = 1, r = x;
    while (l <= r) {
        int m = (l + r) >> 1;
        int left = x / m;
        if (left == m)
            return m;
        else if (left < m)
            r = m - 1;
        else {
            if (x / (m + 1) < (m + 1))
                return m;
            l = m + 1;
        }
    }
    return l;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]快速求解某数的下取整平方根

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/153.html

相关文章