Leetcode69.x的平方根

1.题目描述

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

2.解答

二分查找

我们的一个思路是从一个基数开始,依次进行遍历,求出平方之后和目标值进行比较,直到平方和大于或者等于目标值然后遍历结束,这个想法没有问题,但是如果每个数字依次进行遍历的话效率是非常低的,这时候我们可以使用二分查找的思想,这是我的一个痛点,希望今后可以在一些场景之中考虑到二分查找的使用,昨天阿里二面的时候和面试官在理论上对树以及二分查找的好处以及效率的提升娓娓道来,但是实际手撕代码的时候却没有想到二分查找,不要将原因归结于临场思路阻塞,这说明我的实践能力还是有待提高,废话不多说,我们来看这道题

  • 首先进行边界条件的判断,当x <= 1时,直接返回即可

  • 然后我们可以把右边界right设置为x的一半来进一步减少查找次数

  • 其中需要注意的是,为了应对测试用例中的整数越界,以下两条语句一定要声明为long类型的:

long mid = (left + right + 1) >>> 1; long square = mid * mid;

刚开始我写成这样还是会出现问题:

int mid = (left + right + 1) >>> 1; long square = mid * mid;

我以为既然把square声明了long不就可以了嘛,但是第一个语句的执行是将两个mid计算的结果赋值给square,如果这个数值越界,就不能进行正常的赋值

  • 另外需要注意的一点就是今后进行二分查找找中位数时,尽量使用位运算,要对这种乘以2或者除以2的操作敏感,转换为位运算一定程度上可以提高效率
class Solution {
    public int mySqrt(int x) {
        if(x <= 1)  return x;
        long left = 1;
        long right = x / 2;       
        while(left < right){
            long mid = (left + right + 1) >>> 1;
            long square = mid * mid;
            if(square > x)
                right = mid - 1;
            else 
                left = mid;
        }
        return (int)left;
    }
}

牛顿迭代法

这种方法我允许自己不了解,虽然面试官当时已经提出来了我却没有听说过,还是作为一个技巧了解就好了,看懂上面的推到公式,下一次能够自己进行推到并使用就可以了

image

代码实现起来比较简单:

public class Solution {

    public int mySqrt(int a) {
        long x = a;
        while (x * x > a) {
            x = (x + a / x) / 2;
        }
        return (int) x;
    }
}