LeetCode 补充题 20. 立方根
题目描述
:::fold-green 相关原题
✅ 求解立方根
牛客限定输入绝对值不超过 20，输出保留一位小数；本文函数返回未格式化的近似值。
:::
给定有限实数
x，求它的实数立方根的近似值并返回，即求满足r × r × r = x的实数r。输入可以为正数、负数或零；负数的实数立方根仍是负数。
示例 1：
输入：x = 8.0
输出：2.0
示例 2：
输入：x = -0.125
输出：-0.5
提示：
-
x是有限实数。 - 返回浮点近似值；本题未指定统一的绝对误差或相对误差阈值。
- 示例列出的是对应输入的数学结果。
题意分析
给定实数
x，求它的实数立方根近似值，也就是使r³接近x的数r。立方函数严格递增，所以实数立方根唯一；负数也有实数立方根，其符号与输入相同。CodeTop 只提供了题名，未公布输入范围或误差指标。下方保留固定八十轮浮点二分实现，用来说明区间如何收缩；它的精度取决于输入量级和浮点运算，不能据此承诺对任意量级输入都满足某个统一相对误差。
解法：浮点二分
核心思路
[!blue]
立方函数满足
(-r)³ = -r³，因此先记录输入是否为负，只对target = |x|求非负根，最后恢复符号。这样所有二分比较都可以在非负区间内完成。先建立包含真根的区间
[0, max(1, target)]。当target >= 1时，target³ >= target，所以上界取target足够；当0 <= target < 1时，立方根可能比target大，上界至少取一才能覆盖答案。左端零的立方不大于目标。每轮取中点
mid。如果mid³ < target，由于立方函数递增，根在中点右侧，令left = mid；否则令right = mid。两种更新都在理想实数运算下保留根，并将区间长度减半。这里求的是实数近似值，更新时不能像整数二分那样加一或减一。代码固定执行八十轮，再返回区间中点。若忽略浮点舍入，初始区间宽度为
R，最终宽度为R / 2^80，中点与真根的距离不超过R / 2^81。这个结论说明的是绝对误差与初始范围的关系，而不是任意输入都能保证同样的相对精度。实际计算还受浮点表示和立方乘法的舍入、溢出或下溢影响，不能把理想误差公式当作所有浮点输入的无条件保证。固定轮数能确保循环结束，也避免因等待浮点数恰好相等而无法停止。输入零时，当前代码会得到一个接近零的中点，而不是通过特判直接返回精确零。
解题步骤
- 保存输入符号，令目标为输入的绝对值。
- 初始化
left = 0、right = max(1, target)。- 重复八十轮：计算中点并比较中点的立方与目标，小于目标则更新左端，否则更新右端。
- 取最终区间中点作为根的大小，按原输入符号返回结果。
代码实现
class Solution {
public double cubeRoot(double x) {
// 先分离符号，只在非负区间比较立方
boolean negative = x < 0;
double target = Math.abs(x);
double left = 0.0;
// 小于一时真根可能大于输入，上界至少取一
double right = Math.max(1.0, target);
// 固定轮数得到近似结果，精度仍取决于初始宽度和浮点舍入
for (int i = 0; i < 80; i++) {
double mid = left + (right - left) / 2.0;
if (mid * mid * mid < target) {
left = mid;
} else {
right = mid;
}
}
double root = left + (right - left) / 2.0;
return negative ? -root : root;
}
}
func cubeRoot(x float64) float64 {
// 先分离符号，只在非负区间比较立方
negative := x < 0
target := x
if target < 0 {
target = -target
}
left, right := 0.0, target
// 小于一时真根可能大于输入，上界至少取一
if right < 1 {
right = 1
}
// 固定轮数得到近似结果，精度仍取决于初始宽度和浮点舍入
for i := 0; i < 80; i++ {
mid := left + (right-left)/2
if mid*mid*mid < target {
left = mid
} else {
right = mid
}
}
root := left + (right-left)/2
if negative {
return -root
}
return root
}
复杂度分析
- 时间复杂度：当前实现固定八十轮，为 $O(1)$。若在理想实数运算下按目标绝对误差 $\varepsilon$ 选择轮数，初始宽度为
R，需要 $O(1 + \max(0, \log(R/\varepsilon)))$ 轮。- 空间复杂度：$O(1)$，只维护符号、目标值和少量浮点边界变量。
关键点总结
[!green]
- 先找到包含真根的区间，再利用立方函数的严格单调性决定保留哪一半。
- 绝对值小于一时，不能直接把输入绝对值当作上界，必须覆盖更大的根。
- 八十轮定义了本实现的停止方式；实际精度仍应结合输入范围、误差要求和浮点表示判断。
易错点总结
[!yellow]
- 上界只取
|x|，会排除绝对值介于零和一之间输入的真根。- 边界更新写成
mid + 1或mid - 1，会跳过可能包含实数答案的区间。- 对负数直接套只覆盖非负根的区间，或求完绝对值根后忘记恢复符号，会得到错误方向的结果。
- 用
mid³ == target作为唯一退出条件，不能保证浮点运算一定恰好命中。- 把固定轮数、理想算术的绝对误差和实际浮点相对误差混为一谈，会夸大这段实现能够保证的精度范围。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 69. x 的平方根 | 简单 | 都对单调幂函数二分，本题求实数近似且支持负数，整数平方根题返回下取整值。 |
| 补充题 149. 实数平方根的近似计算 | 中等 | 都需明确浮点误差或迭代终止条件，本题把平方关系改成立方，负值通过符号恢复处理。 |