题目地址(69. Sqrt(x))

https://leetcode-cn.com/problems/sqrtx/

题目描述

  1. 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
  3. 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
  5. 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
  9. 示例 1：
  11. 输入：x = 4
  12. 输出：2
  15. 示例 2：
  17. 输入：x = 8
  18. 输出：2
  19. 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
  24. 提示：
  26. 0 <= x <= 231 - 1

前置知识


公司

  • 暂无

思路

使用二分查找的方式 如果x小于中值相乘就让max等于中值 快速的求出值

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.     public int mySqrt(int x) {
  4.         //如果x=1的话 返回1
  5.         if(x==1){
  6.             return 1;
  7.         }
  8.         int min = 0;
  9.         int max = x;
  10.         while(max-min>1){
  11.             int f = (min+max)/2;
  12.             //使用x/f<f而不是x<f*f是因为防止溢出
  13.             if(x/f<f){
  14.                 max = f;
  15.             }else{
  16.                 min = f;
  17.             }
  18.         }
  19.         return min;
  20.     }
  21. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：69. Sqrt(x) - 图1#card=math&code=O%28logn%29&id=blhgo)
  • 空间复杂度：69. Sqrt(x) - 图2#card=math&code=O%28n%29&id=XjxJ9)