0%

2020-01-15-sqrtx

LeetCode-69

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 1:

Input: 4
Output: 2
Example 2:

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

Solution

就是手写一个根号源码,首先想到的就是通过平方来做

1
2
3
4
5
6
7
8
9
10
public int mySqrt(int x) {
for(int i=46340;i<46341;i++){
if(x>=(long)i*i&&x<(long)(i+1)*(i+1)){
return i;
}
}
return x;
}
Runtime: 22 ms
Memory Usage: 34 MB

如果不遵循题目的要求,使用Math函数,所以我们的目标大概是3ms附近

1
2
3
4
public int mySqrt(int x) {
return (int)Math.sqrt(Double.parseDouble(String.valueOf(x)));
}
Runtime: 3 ms

解法粗暴,遇到大数的时候会从0重新开始计算,复杂度O(N)

第一次优化

思路就是避免做两次乘法然后去比较,这个地方可以去优化

1
2
3
4
5
6
7
8
9
10
class Solution {
public int mySqrt(int x) {
long n = 1;
while(n * n <= x) {
n++;
}
return (int) n - 1;
}
}
Runtime: 11 ms

第二次优化

可以使用二分法来逐步逼近i,没有必要从1开始顺序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1) return x;

int left = 1;
int right = x;
while (left < right) {

int midPoint = (left + right) / 2;
if (midPoint == x / midPoint) {
return midPoint;
} else if (midPoint > x / midPoint) {
right = midPoint;
} else if (midPoint < x / midPoint) {
left = midPoint + 1;
}
}

return left - 1;
}
}
Runtime: 1 ms