sqrt

Sqrt(x) – LeetCode 69

Problem

Description

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example

Example 1:
Input: 4
Output: 2

Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we want to return an integer, the decimal part will be truncated.

Answer

Original

Code

class Solution {
public:
    int mySqrt(int x) {
        long long n = 0;
        while((n * n) <= x){
            ++n;
        }
        return n - 1;
    }
};

思路

简单的从0开始递增尝试，最差的方法，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$32$ ms，排名$96.51\%$

Better

思路

• 二分法
  基本操作。时间复杂度$O(\log_{2}{n})$，空间复杂度$O(1)$。
  耗时$15$ ms，排名$91.68\%$

• 牛顿迭代法
  详见Wiki
  耗时$19$ ms，排名$92.90\%$

• 位操作
  通过从高位到低位依次尝试来猜测答案，时间复杂度$O(\frac{1}{2}\log_{2}{n})$，空间复杂度$O(1)$。
  耗时$19$ ms，排名$92.90\%$

Code

• 二分法

class Solution {
public:
    int mySqrt(int x) {
        long i = 0;  
        long j = x / 2 + 1;  
        while (i <= j) {  
            long mid = (i + j) / 2;  
            if (mid * mid == x)  
                return (int)mid;  
            if (mid * mid < x)  
                i = mid + 1;  
            else  
                j = mid - 1;  
        }  
        return (int)j;
    }
};

• 牛顿迭代法

class Solution {
public:
    int mySqrt(int x) {
        if (x ==0)  
            return 0;  
        double pre;  
        double cur = 1;  
        do  
        {  
            pre = cur;  
            cur = x / (2 * pre) + pre / 2.0;  
        } while (abs(cur - pre) > 0.00001);  
        return int(cur);  
    }
};

• 位操作

class Solution {
public:
    int mySqrt(int x) {
        unsigned long ans = 0;  
        unsigned long bit = 1u << 16;  
        while(bit > 0) {  
            ans |= bit;  
            if (ans * ans > x) {  
                ans ^= bit;  
            }  
            bit >>= 1;  
        }  
        return ans;   
    }
};