题解 | #求平方根#

思路:

从题中给出的有效信息：

• 取x的平方根向下取整

最好不要使用库函数，这是面试官不想看到的，仔细分析此题，不难发现此题有两个信息点：
1.x>4时，x的平方根一定不会超过它的一半,
2.自然数的平方是递增的，它是一个有序的排序；
基于两点信息可以使用 二分法 来进行求解此题

方法一：二分法

具体做法：
每次取x的一半 right ，判断 left 的值 与 right 除以 mid 向下取整 的比较方向，进行二分；

import java.util.*;
public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        if (x < 2) {
            return x;
        }
        int left = 1;
        int right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            int sqrtTemp= x / mid;
            if (mid > sqrtTemp) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

复杂度分析：

• 时间复杂度：O(logn)，因为每一次在进行遍历时都是上次的一半，常数省略为O(logn)
• 空间复杂度：O(1)

方法二：直接遍历

具体做法：
从0开始遍历√x个数据；

import java.util.*;
public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        int res = 0;
        // 注意转换为 long, 否则会产生溢出
        while ((long)res * res <= x) {
            ++res;
        }
        return --res;
    }
}

复杂度分析：

• 时间复杂度：O(√x) 从0开始遍历√x次，常数单位
• 空间复杂度：O(1) 未申请额外空间