Implement int sqrt(int x)
.
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4 Output: 2
Example 2:
Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
分析¶
这道题目可以使用二分查找,唯一需要注意的就是整数值可能过大,所以这里当计算平方的时候采用double类型防止两个整数相乘溢出。
public int mySqrt(int x) { int lo = 1, hi = x; while (lo <= hi) { int mid = (lo + hi) >>> 1; double cmp = ((double) mid)* mid - x; if (cmp > 0) hi = mid - 1; else if (cmp < 0) lo = mid + 1; else return mid; } return lo - 1; }
在比较数字的时候,采用除法更好一些,避免了int类型的转换,和double类型的保存:
public int mySqrt(int x) { int lo = 1, hi = x; while (lo <= hi) { int mid = (lo + hi) >>> 1; int cmp = mid - x/mid; if (cmp > 0) hi = mid - 1; else if (cmp < 0) lo = mid + 1; else return mid; } return lo - 1; }
近期评论