Task

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

Example 1:

1
2

Input: 4
Output: 2

Example 2:

1
2
3
4

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

Solution

暴力搜索

  • 从0开始向右搜索并平方，从平方值小于x跳变到平方值大于x时即是所求点
  • 时间复杂度：搜到sqrt{x}时停止，时间复杂度为O(sqrt{n})
  • 空间复杂度：不需引入额外变量，O(1)
  • 实现1（用long long避免平方溢出）：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Runtime: 20 ms, faster than 11.31% of C++ online submissions for Sqrt(x).
// Memory Usage: 5.9 MB, less than 82.79% of C++ online submissions for Sqrt(x).
class Solution {
public:
    int mySqrt(int x) {
        //边界情况
        if(x==0 || x==1)
            return x;
        //使用更长的整型避免溢出
        long long i=1;
        while(i*i<=x)
            ++i;
        return i-1;
    }
};
  • 实现2（用除法避免溢出）：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Runtime: 64 ms, faster than 5.11% of C++ online submissions for Sqrt(x).
// Memory Usage: 6.1 MB, less than 30.77% of C++ online submissions for Sqrt(x).
class Solution {
public:
    int mySqrt(int x) {
        //边界情况
        if(x==0 || x==1)
            return x;
        int i=1;
        //使用除法避免溢出
        while(i<=x/i)
            ++i;
        return i-1;
    }
};

二分查找

  • 类似暴力搜索查找分界点：中点平方小于x时取右侧区间，中点平方大于x时取左侧区间。查找的终止条件是区间缩小为一个点
  • 时间复杂度：二分搜索，O(logn)
  • 空间复杂度：无额外开销，O(1)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sqrt(x).
// Memory Usage: 5.9 MB, less than 78.70% of C++ online submissions for Sqrt(x).
class Solution {
public:
    int mySqrt(int x) {
        //边界情况
        if(x==0 || x==1)
            return x;
        //两端闭区间
        int l=1,r=x;
        while(l<r){
            //这里使用插值形式l+(r-l)/2而非平均形式(l+r)/2，原因是相加可能溢出，相减不会
            long long m=l+(r-l)/2;
            //由于m是向下取整，故缩小区间时只能l=m+1，若用l=m则在l和r相邻时死循环
            if(m*m<=x)
                l=m+1;
            else
                r=m;
        }
        return l-1;
    }
};

牛顿法

  • 根据牛顿法迭代求根公式：$$x_{n+1}=x_n-\frac{f(x_n)}{f’(x_n)}$$
  • 求$\sqrt{a}$时建立方程：$f(x)=x^2-a=0$，故牛顿公式化为：$$x_{n+1}=x_n-\frac{x_n^2-a}{2x_n}=\frac{1}{2}(x_n+\frac{a}{x_n})$$
  • 根的初始值设为a，epsilon控制误差
  • 实现1（用浮点型算迭代）：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sqrt(x).
// Memory Usage: 5.9 MB, less than 61.78% of C++ online submissions for Sqrt(x).
class Solution {
public:
    int mySqrt(int x) {
        //设定初始值和epsilon
        double m=x;
        const double eps=1e-3;
        //迭代
        while(abs(m*m-x)>eps)
            m=(m+x/m)/2;
        return static_cast<int>(m);
    }
};
  • 实现2（用整型算迭代）：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// Runtime: 4 ms, faster than 59.65% of C++ online submissions for Sqrt(x).
// Memory Usage: 5.9 MB, less than 61.78% of C++ online submissions for Sqrt(x).
class Solution {
public:
    int mySqrt(int x) {
        //从右侧逼近
        long long m=x;
        //不用epsilon控制误差，只要求迭代点落在根的右侧
        while(m*m>x)
            m=(m+x/m)/2;
        return m;
    }
};