【Description】
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.
【AC code】
一、暴力法 时间复杂度：O(sqrt(x))
1 class Solution { 2 public int mySqrt(int x) { 3 if (x <= 1) return x; 4 int t = 1; 5 while (x / t >= t) t++; 6 return t - 1; 7 } 8 }
二、二分查找法 时间复杂度：O(logn)
1 class Solution { 2 public int mySqrt(int x) { 3 if (x <= 1) return x; 4 int left = 1, right = x; 5 while (left <= right) { 6 int mid = left + (right - left) / 2; 7 if (x / mid > mid) left = mid + 1; 8 else if (x / mid < mid) right = mid - 1; 9 else return mid; 10 } 11 return left - 1; 12 } 13 }
三、牛顿迭代法 时间复杂度：O(logn)
Reference: https://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html
1 class Solution { 2 public int mySqrt(int x) { 3 if (x <= 1) return x; 4 long t = x; //测试用例中x的最大值为INT_MAX,为避免后续(t + x / t)数据溢出采用long。 5 while (x / t < t) { 6 t = (t + x / t) / 2; 7 } 8 return (int)t; 9 } 10 }
原文：https://www.cnblogs.com/moongazer/p/11514565.html
