第一种自然就是调 API 啦(手动滑稽)
- public int mySqrt(int x) {
- return (int)Math.sqrt(x);
- }
时间是 52 ms, 还超过了 1/5 的人呢
第二种 二分法
就是在 0--X 之间一半地一半地砍, 最后直到左右边界的中间的数 = X/mid, 这样做是防止因为 mid 数字太大而导致溢出
看代码吧, 跟排序类似
- public int getSqrtByDevide(int x) {
- if (x<=1) {
- return x;
- }
- int low = 0;
- int high = x;
- int mid = 0;
- while(low<=high) {
- mid = low + (high - low)/2;
- if(mid == (x/mid))
- return mid;
- else if(mid <(x/mid))
- low = mid + 1;
- else
- high = high -1;
- }
- return high;
- }
这种比上种稍微快一点: 45 ms
第三种 牛顿迭代法
刚开始还没搞懂是怎么回事, 后来看了网上的一些帖子才明白.
首先拿此题来说, 假设最后的输出的结果 x² = N,(N 是函数参数终点 x), 这里可以看成一个函数, 即 f(x) = x² - N;
那么最终的目的就变成了求这个函数的零点了
迭代过程就是从 X0 开始, 看它的平方是不是等于 N, 是就返回, 不是就在 X0 对应的在函数图像上的点上做切线
再求这个切线和 x 轴的交点, 重复上面的步骤:
f(x) = x² - N
设点 Xi, 则经过点 (Xi,f(Xi)) 处的切线方程为 g(x) = f(Xi)+ f'(Xi)(x - Xi)
令 g(x) = 0
得 x = Xi - f(Xi)/f'(Xi)
又 f(Xi) = Xi² - N
代入得最终迭代式子:
x = (Xi + N/Xi)/2;
然后代码:
- public int getSqrtByNewton(int x) {
- if (x<=1) {
- return x;
- }
- double last = -1;// 最后
- double ans = 1;// 结果
- while(last!=ans) {
- last = ans;// 将迭代前的 ans 存起来, 如果和迭代后 ans 相等, 代表非常逼近
- ans = (ans+x/ans)/2;
- }
- return (int)ans;
- }
这个还是很快的: 27ms
第四种 "0x5f3759df" 算法
这个的原理我也没搞太清楚, 好像有个专门的论文将这个算法的, 很神奇, 经常用于图形学游戏领域一些场景里面
那我就只贴个代码吧(凑个字数...)
- public int mySqrt(int x) {
- long t = x;
- t = 0x5f3759df - (t>> 1);
- while (!(t*t <= x && (t+1)*(t+1)> x))
- t = (x/t + t)/2;
- return (int)t;
- }
这里有讲, 挺麻烦的, 我就知道打一波 666 吧...
来源: https://www.cnblogs.com/Yintianhao/p/10589762.html