NC32 求平方根

  算法   1分钟   330浏览   0评论

题目链接:https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c

题目描述

实现函数 int sqrt(int x).

计算并返回 x 的平方根(向下取整)

数据范围: 0 <= x < 2^31−1

要求:空间复杂度 O(1),时间复杂度 O(logx)

示例 1:

输入:2
返回值:1

示例 2:

输入:2143195649
返回值:46294

解题代码

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        // x不能为0
        if (x <= 0) {
            return 0;
        }
        int res = x;
        // 利用牛顿迭代式进行求解
        while (res > x / res) {
            res = (res + x / res) / 2;
        }
        return res;
    }
}

如果你觉得文章对你有帮助,那就请作者喝杯咖啡吧☕
微信
支付宝
  0 条评论