题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4 输出: 2

示例 2:

输入: 8 输出: 2 说明: 8 的平方根是 2.82842...,

由于返回类型是整数，小数部分将被舍去。

题解

方法一：二分查找

找到中间的数: mid = start + (end - start) / 2 而且: mid * mid <= x && (mid + 1) * (mid + 1) > x 但是这么写超出了 Integer 的范围了:

class Solution { public int mySqrt(int x) { if (x == 0) return 0; int start = 1, end = x; while (start < end) { int mid = start + (end - start) / 2; if (mid * mid <= x && (mid + 1) * (mid + 1) > x)// Found the result return mid; else if (mid > x / mid)// Keep checking the left part end = mid; else start = mid + 1;// Keep checking the right part } return start; } }

所以改变一下: mid * mid <= x && (mid+1)(mid+1) > x 下面的 code 为 AC 版本:

class Solution { public int mySqrt(int x) { if (x == 0) return 0; int start = 1, end = x; while (start < end) { int mid = start + (end - start) / 2; if (mid <= x / mid && (mid + 1) > x / (mid + 1))// Found the result return mid; else if (mid > x / mid)// Keep checking the left part end = mid; else start = mid + 1;// Keep checking the right part } return start; } }

python 版本

class Solution: def mySqrt(self, x): start, end = 0, x while start <= end: # 结果都计算为整数 mid = start + (end - start) // 2 if mid * mid <= x < (mid + 1) * (mid + 1): return mid elif x < mid * mid: end = mid else: start = mid + 1

牛顿迭代法

基本思想：把非线性方程线性化，用线性方程的解逐步逼近原方程的解

求某个数(比如 8)的平方根其实就是求解 f(x) = x^2 - 8 = 0 的解

如上图

点(x[k+1], 0)满足该方程 0 = f （ x[k]） + f'(x[k])(x[k+1] - x[k]) 得到牛顿迭代法的迭代公式:

x[k+1] = x[k] - f(x[k]) / f'(x[k])

回到求 8 的平方根

x[k+1] = x[k] - (x[k] - 8) / (2 * x[k]) = (x[k] + 8 / x[k]) / 2

就这样一直逼近到 x[k] * x[k] <= 8

class Solution { public int mySqrt(int x) { if (x == 0) return 0; long i = x; while(i > x / i) i = (i + x / i) / 2; return (int)i; } }

python 版本

class Solution: def mySqrt(self, x): """ :type x: int :rtype: int """ if x == 0: return 0 i = x while int(i) > int(x / i): i = (i + x / i) / 2 return int(i)