LeetCode 69. x 的平方根

Categories:

Tags:

题目描述
思路分析
参考代码
相似题目

题目描述

🔥 69. x 的平方根

思路分析

使用二分查找法来寻找平方根的整数部分。

初始化左右边界 left 和 right，分别为 0 和 x。

计算中间值 mid，并判断 mid 的平方是否小于等于 x。

如果 mid 的平方小于等于 x，则将左边界 left 移动到 mid + 1；否则将右边界 right 移动到 mid - 1。

最终返回右边界 right 即为平方根的整数部分。

参考代码

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

时间复杂度: O (log n)，其中 n 是输入的整数 x。二分查找的时间复杂度为对数级别。

空间复杂度: O (1)，我们只使用了常数级别的额外空间。

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

🍏 点击查看 Java 题解

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

相似题目

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/58773597