题目大意：让你实现开根号函数，只需要返回整数部分。
Problem:
Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.
Example 1:
|
1 2 |
Input: 4 Output: 2 |
Example 2:
|
1 2 3 |
Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842... |
Solution 1: Brute force
Time complexity: sqrt(x)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua // Running time: 40 ms class Solution { public: int mySqrt(int x) { if (x <= 1) return x; for (long long s = 1; s <= x; ++s) if (s * s > x) return s - 1; return -1; } }; |
C++ div
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua // Running time: 162 ms class Solution { public: int mySqrt(int x) { if (x <= 1) return x; for (int s = 1; s <= x; ++s) if (s > x / s) return s - 1; return -1; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua // Running time: 71 ms class Solution { public int mySqrt(int x) { if (x <= 1) return x; for (long s = 1; s <= x; ++s) if (s * s > x) return (int)s - 1; return -1; } } |
Python3 TLE
|
1 2 3 4 5 6 7 8 9 10 11 12 |
""" Author: Huahua TLE: 602 / 1017 test cases passed. """ class Solution: def mySqrt(self, x): if x <= 1: return x s = 1 while True: if s*s > x: return s - 1 s += 1 return -1 |
Solution 2: Binary search
Time complexity: O(logn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 12 ms class Solution { public: int mySqrt(int x) { long l = 1; long r = static_cast<long>(x) + 1; while (l < r) { long m = l + (r - l) / 2; if (m * m > x) { r = m; } else { l = m + 1; } } // l: smallest number such that l * l > x return l - 1; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 47 ms class Solution { public int mySqrt(int x) { int l = 1; int r = x; while (l <= r) { int m = l + (r - l) / 2; if (m > x / m) { r = m - 1; } else { l = m + 1; } } return r; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
""" Author: Huahua Running time: 119 ms """ class Solution: def mySqrt(self, a): l = 1 r = a while l <= r: m = l + (r - l) // 2 if m * m > a: r = m - 1 else: l = m + 1 return r; |
Solution 3: Newton’s method
C++ / float
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 28 ms class Solution { public: int mySqrt(int a) { constexpr double epsilon = 1e-2; double x = a; while (x * x - a > epsilon) { x = (x + a / x) / 2.0; } return x; } }; |
C++ / int
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 27 ms class Solution { public: int mySqrt(int a) { // f(x) = x^2 - a, find root of f(x) // Newton's method // f'(x) = 2x // x' = x - f(x) / f'(x) = x - (1/2*x - a/(2*x)) // = (x + a / x) / 2 int x = a; while (x > a / x) x = (x + a / x) / 2; return x; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua // Running time: 44 ms class Solution { public int mySqrt(int a) { long x = a; while (x * x > a) x = (x + a / x) / 2; return (int)x; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
""" Author: Huahua Running time: 100 ms """ class Solution: def mySqrt(self, a): x = a while x * x > a: x = (x + a // x) // 2 return x |