LeetCode 69. x 的平方根

2026-09-03 HGNULB 约 4 分钟

文章信息 23 个分类 5 个标签

分类

LeetCode CodeTop 简单已解决已掌握 100-200 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴京东拼多多小米商汤虾皮小红书作业帮面试经典 150 题

题目描述

✅ 69. x 的平方根

题意分析

给定非负整数 x（范围可达 2^31 - 1），返回它的算术平方根，且「只保留整数部分」——这就是向下取整：要找的是满足 ans * ans <= x 的最大非负整数 ans。

题目明确禁止调用 pow(x, 0.5)、x ** 0.5 这类内置函数，这个限制本身就是信号：考的是自己实现「找这个最大整数」的过程，而不是调库。

约束上界 2^31 - 1 提示两个隐患：一是候选值的平方很容易超出 int 范围，直接相乘会溢出成负数干扰判断；二是逐个尝试的次数可达几万级，需要更快的收缩方式。

边界：x = 0 答案为 0，x = 1 答案为 1；x = 8 这类非完全平方数用来验证「向下取整」——答案是 2 而不是 3。

解法：二分查找最大可行值

核心思路

答案是满足 k² <= x 的最大整数 k。这个条件随 k 单调变化，因此可以二分查找最后一个可行值。

为避免平方溢出，Java 使用 long 计算 mid * mid；Go 使用 mid <= x / mid 判断。

解题步骤

x < 2 时直接返回 x。

在 [1, x / 2] 内二分，ans 记录当前最大的可行值。

若 mid² <= x，更新 ans 并继续搜索右半区间；否则搜索左半区间。

区间为空时返回 ans。

代码实现

class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }

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

func mySqrt(x int) int {
    if x < 2 {
        return x
    }

    left, right, ans := 1, x/2, 1
    for left <= right {
        mid := left + (right-left)/2
        if mid <= x/mid {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

复杂度分析

时间复杂度：$O(\log x)$。

空间复杂度：$O(1)$。

关键点总结

将问题转化为“查找最后一个满足条件的值”。

可行时继续向右搜索，并用 ans 保存结果。

平方比较必须防止整数溢出。

易错点总结

直接用 int 计算 mid * mid，可能溢出并造成错误判断。

找到一个可行值就立即返回，得到的不一定是最大可行值。

返回退出时的 left 会多 1，应返回 ans 或 right。

使用除法判断时必须保证 mid > 0，避免除零。

相似题目

题目	难度	考察点
410. 分割数组的最大值	困难	二分答案 + 贪心划分子数组判定
644. 子数组最大平均数 II	困难	实数域二分 + 前缀和判平均值
668. 乘法表中第k小的数	困难	二分第 k 小 + 按行计数
719. 找出第 K 小的数对距离	困难	二分距离 + 排序双指针计数
774. 最小化去加油站的最大距离	困难	实数二分 + 按误差精度终止
875. 爱吃香蕉的珂珂	中等	二分最小速度 + 上取整耗时判定
878. 第 N 个神奇数字	困难	二分 + 容斥原理计数与取模
1011. 在 D 天内送达包裹的能力	中等	二分最小载重 + 顺序装载模拟
1201. 丑数 III	中等	二分 + 最小公倍数三集合容斥
1231. 分享巧克力	困难	最大化最小值 + 贪心切分计块
1482. 制作 m 束花所需的最少天数	中等	二分天数 + 连续开花段统计
1552. 两球之间的磁力	中等	最大化最小间距 + 贪心放置判定
LCP 12. 小张刷题计划	中等	二分每天耗时上限 + 一次求助的贪心
LCR 072. x 的平方根	简单	本题镜像题，解法完全一致
LCR 073. 爱吃香蕉的狒狒	中等	875 的镜像题，速度下界二分
补充题 7. 木头切割问题	中等	二分切割长度 + 段数达标判定
补充题 20. 立方根	中等	实数二分求立方根 + 精度控制