zkkKillua's Blog
0%

69.x的平方根

发表于 更新于 分类于

1. 二分

时间复杂度：O(logn)，空间复杂度O(1)。 

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

        int left = 0, right = x;
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long long midv = (long long)mid * mid;
            if (midv == x) {
                ans = mid;
                break;
            } else if (midv < x) {
                ans = mid;
                left = mid + 1;
            } else 
                right = mid - 1;
        }

        return ans;
    }
};