2020-01-15-sqrtx

Posted on Edited on In

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