LeetCode 69. Sqrt(x) [Easy] [C++] 解題筆記

這題給定一個整數 n 要我們求平方根。

EX:

       Input: 4

 

Ans: 2

想法:

        這裡我們可以反過來想，用 binary search 在 1~n 之間找平方最接近X的數。

另一種作法是利用數學方法，就是牛頓逼近法(Newton's method)來求解，因為求 n 的平方根等於求解 x^2 = n => f(x) = x^2 - n 等於0的解，因此透過牛頓法可以知道求解公式為:

x_i+1=x_i - (x_i² - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2

牛頓法的詳細推導可以參考維基百科:

https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95

完整程式碼:

解法一 ( Binary Search ):

class Solution {

public:

    int mySqrt(int x) {

        if (x <= 1) { return x; }

        int left = 0;

        int right = x;

            

        while (left <= right) {

            int mid = left + (right - left) / 2;

            if (x / mid >= mid) {

                left = mid + 1;

            }   

            else {

                right = mid - 1;

            }   

        }   

            

        return left - 1;

    }   

};

解法二 (Newton's method):

class Solution {

public:

    int mySqrt(int x) {

        double ans = x;

        double delta = 0.00001;

        while (fabs(ans*ans - x) > delta) {

            ans = (ans + x / ans) / 2;

        }

        return ans;

    }

};