LeetCode 69. Sqrt(x)

Description

Implement int sqrt(int x). Compute and return the square root of x.

my program

思路：看似很简单的问题，可以不断的优化算法，最开始容易想到的是定义一个num使其递增，直到num*num > x，可是未考虑num*num越界的问题，后更改判断条件为num <= x/num，可以消除越界问题。但是此算法超出此题要求的时间范围，即Time Limit Exceeded。

class Solution { public: int mySqrt(int x) { if(0 == x) return 0; int num = 1; while(num <= x/num){ num++; } if(num*num == x) return num; else return num-1; } };

Submission Details 1017 / 1017 test cases passed. Status: Time Limit Exceeded Last executed input: 1579205274

二分法

时间复杂度为O(logN)，这样就不会Time Limit Exceeded

class Solution { public: int sqrt(int x) { double begin = 0; double end = x; double result = 1; double mid = 1; while(abs(result-x) > 0.000001){ mid = (begin+end)/2; result = mid*mid; if(result > x) end = mid; else begin = mid; } return (int)mid; } };

Submission Details 1017 / 1017 test cases passed. Status: Accepted Runtime: 6 ms

牛顿迭代法

牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

class Solution { public: int mySqrt(int x) { long r = x; while (r*r > x) r = (r + x/r) / 2; return r; } };

Submission Details 1017 / 1017 test cases passed. Status: Accepted Runtime: 6 ms