NC32 题解 | #求平方根#

题意分析

• 这个题目题目意思很简洁，就是让我们求出一个数的开根号之后的数据，向下进行取整。

思路分析

解法一 二分

• 我们发现，最后的答案具有单调性，当我们求出某一个数字为mid的时候，我们可以和给出的数字进行比较，判断这个数字是大了还是小了，从而移动我们的边界。这样通过左右边界的移动我们最后就可以不断逼近最后的终点了。

• 代码如下,
  • 二分的时间复杂度为O(logn)
  • 只开了几个变量，空间复杂度为O(1)

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        // 特判
        if(x<=0){
            return 0;
        }
        // 利用二分进行求解
        int l=1,r=x,mid;
        while(1){
            mid=(l+r)>>1;
            // 这个地方需要好好理解一下，因为题目上面说是进行向下取整
            if(mid<=x/mid&&(mid+1)>x/(mid+1)){
                return (int)mid;
                // 找到的点过小
            }else if(mid<x/mid){
                l=mid+1;
            // 找到的点过大
            }else{
                r=mid-1;
            }
        }
    }
};

解法二 数学定理

• 我们首先需要了解一个牛顿迭代公式。（部分图片来自百度)

知道了这个之后，我们就可以根据这个公式进行求解了。

• 代码如下
  • 二分的时间复杂度为O(logn)
  • 只开了几个变量，空间复杂度为O(1)。

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        // 特判0的情况
        if(x<=0){
            return 0;
        }
        int r=x;
        // 利用牛顿迭代式进行求解
        while(r>x/r){
            r=(r+x/r)/2;
        }
        return int(r);
    }
};