Leetcode 题目解析之 Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

代码语言：javascript复制

    public int mySqrt(int x) {
        // 首先对负数和0进行处理
        if (x < 0) {
            return -1;
        } else if (x == 0) {
            return 0;
        }
        int start = 1;
        int end = x;
        while (start < end) {
            // 不能直接相加除以2，因为两个数相加可能溢出
            int m = start   (end - start) / 2;
            // 不能用m^2，(m 1)^2，因为可能溢出
            int m1 = x / m;
            int m2 = x / (m   1);
            // m*2 == x
            if (m == m1) {
                return m;
            }
            // (m 1)^2 == x
            if (m   1 == m2) {
                return m   1;
            }
            // m*2 <= x && (m 1)^2 > x
            if (m < m1 && m   1 > m2) {
                return m;
            }
            // m*2 > x
            if (m1 < m) {
                end = m;
            } else {
                // (m 1)^2 < x
                start = m   1;
            }
        }
        return 1;
    }

int return root

0 人点赞