剑指 Offer II 072. 求平方根

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 根号 8 是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

注意：本题与主站 69 题相同： https://leetcode.cn/problems/sqrtx/

解法

方法一

思考

求 \(\lfloor\sqrt{x}\rfloor\)。从 \(1\) 累加到答案是 \(O(\sqrt{x})\)。

所求是满足 \(mid\le x/mid\) 的最大整数。二分时用除法代替乘法，避免溢出；取上中位数以便在左闭右闭区间上收缩到该最大值。

Python3JavaC++GoJavaScriptC#Swift

class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left < right:
            mid = (left + right + 1) >> 1
            # mid*mid <= x
            if mid <= x // mid:
                left = mid
            else:
                right = mid - 1
        return left

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x;
        while (left < right) {
            int mid = (left + right + 1) >>> 1;
            if (mid <= x / mid) {
                // mid*mid <= x
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

class Solution {
public:
    int mySqrt(int x) {
        long long left = 0, right = x;
        while (left < right) {
            long long mid = left + ((right - left + 1) >> 1);
            if (mid <= x / mid)
                left = mid;
            else
                right = mid - 1;
        }
        return (int) left;
    }
};

func mySqrt(x int) int {
    left, right := 0, x
    for left < right {
        mid := left + (right-left+1)>>1
        if mid <= x/mid {
            left = mid
        } else {
            right = mid - 1
        }
    }
    return left
}

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
    let left = 0;
    let right = x;
    while (left < right) {
        const mid = (left + right + 1) >>> 1;
        if (mid <= x / mid) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
};

public class Solution {
    public int MySqrt(int x) {
        int left = 0, right = x;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (mid <= x / mid) {
                left = mid;
            }
            else {
                right = mid - 1;
            }
        }
        return left;
    }
}

class Solution {
    func mySqrt(_ x: Int) -> Int {
        if x == 0 {
            return 0
        }
        var left = 0
        var right = x
        while left < right {
            let mid = (left + right + 1) / 2
            if mid <= x / mid {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left
    }
}

剑指 Offer II 072. 求平方根

题目描述

解法

方法一

评论