0%

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

1
2
3
4
5
6
7
8
9
10
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

  • 二分法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}
};
  • 牛顿迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
}
};
  • 位操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}
};