我对 Leetcode 谜题 Sqrt(x) 的解决方案有什么问题？

Question

我正在做题为 sqrt(x)(https://leetcode.com/problems/sqrtx/) 的 LeetCode 第 69 题。它要求我return 整数的平方根也在另一个整数中。以下是我的解决方案。

public class Solution {
    public int mySqrt(int x) {
    int i = 0;
    if(x==0)
    {
        return 0;
    }
    for(i = 1;i<x/2;i++)
    {
        if(((i*i)<=x)&&((i+1)*(i+1)>x))
        {
            break;
        }
    }

    return i;
   }
}

我提交代码后，所有x >= 2147395600的测试用例都失败了。当 x = 2147395600 时，它是 returning 289398 而不是 46340，这是正确的答案。我的代码有什么问题？

Answer 1

你可以试试我的代码：

public int mySqrt(int x) {
        long i = 0;
        long j = x;
        int mid = 0;
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }
        while (i <= j) {
            mid = (int)(i + j)/2;
            if (x/mid == mid) {
                return (int)mid;
            } else if (x/mid > mid) {
                i = mid + 1;
            } else if (x/mid < mid) {
                j = mid - 1;
            }
        }
        return (int)j;
        }

Answer 2

使用 long 而不是 int。这是因为 int 仅上升到 2147395600，而 long 远高于此。但是，代价是您必须先转换为 long，然后再转换回 int。

Answer 3

我遇到了同样的问题，但只需在 ii 表达式前添加一个类型转换（long），我就解决了。问题在于 ii 超出了 int 可以保存的值的限制，因此返回了垃圾值。

PS：此解决方案非常慢，因此请考虑其他解决方案，例如上面提供的二进制搜索。

我对 Leetcode 谜题 Sqrt(x) 的解决方案有什么问题？

What is wrong of my solution for the Leetcode puzzle Sqrt(x)?

java

sqrt