LeetCode 补充题 20. 立方根

Categories:

题目描述
思路分析
1. 解法一：二分查找（推荐）
相似题目

题目描述

✅ 补充题 20. 立方根

思路分析

解法一：二分查找（推荐）

核心思路：

目标函数 f(x) = x^3 单调递增，可用二分查找。

通过 mid^3 与目标值比较，缩小搜索区间。

用 long 计算，避免中间溢出。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示输入的绝对值。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int cubeRoot(int x) {
        long target = Math.abs((long) x);
        long left = 0;
        long right = target;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long cube = mid * mid * mid;

            if (cube == target) {
                return x < 0 ? (int) -mid : (int) mid;
            } else if (cube < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        int res = (int) right;
        return x < 0 ? -res : res;
    }
}

func cubeRoot(x int) int {
    target := int64(x)
    if target < 0 {
        target = -target
    }

    left, right := int64(0), target
    for left <= right {
        mid := left + (right-left)/2
        cube := mid * mid * mid

        if cube == target {
            if x < 0 {
                return int(-mid)
            }
            return int(mid)
        } else if cube < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    res := int(right)
    if x < 0 {
        return -res
    }
    return res
}

相似题目

题目	难度	考察点
69. x 的平方根	简单	二分查找
367. 有效的完全平方数	简单	二分查找
50. Pow(x, n)	中等	快速幂
29. 两数相除	中等	二分查找
875. 爱吃香蕉的珂珂	中等	二分答案

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/37081036