【Day 37 】2024-05-14 - 69. x 的平方根

[azl397985856]

69. x 的平方根

入选理由

暂无

题目地址

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

前置知识

• 二分法

  题目描述

  
  实现 int sqrt(int x) 函数。

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

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

示例 1:

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

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

[lxy1108]

思路

二分查找

python3代码

class Solution:
    def mySqrt(self, x: int) -> int:
        l,r=1,x
        while l<=r:
            mid = (l+r)//2
            if mid**2 == x:
                return mid
            if mid**2 < x:
                l = mid+1
            else:
                r = mid-1
        return r

复杂度分析

时间复杂度 o(logx) 空间复杂度o(1)

[YYYYYTC]

二分查找法 class Solution { func mySqrt(_ x: Int) -> Int { if x < 2 { return x }

var left = 1
var right = x / 2

while left <= right {
    let mid = left + (right - left) / 2
    let square = mid * mid
    if square == x {
        return mid
    } else if square < x {
        left = mid + 1
    } else {
        right = mid - 1
    }
}

return right

} } o(logx) o(1)

[rao-qianlin]

思路

二分查找 需要注意溢出问题

代码

class Solution {
    public int mySqrt(int x) {
        if(x==0 || x==1){
            return x;
        }

        int left = 1;
        int right = x/2;

        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if( mid > x/mid){
                right = mid -1;
            }else{
                left = mid;
            }
        }

        return left;

    }
}

[yashuning]

思路：二分查找 代码：

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:return x 
        start,end = 1,x 
        while start<end:
            mid = (start + end + 1) // 2
            if mid ** 2 <= x:
                start = mid
            else:
                end = mid - 1
        return start

时间复杂度：Ologn

[xil324]

··· class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ if x < 2: return x left, right = 2, x//2

    while left <= right:
        mid = (left + right) //2
        if mid * mid > x:
            right = mid -1
        elif mid * mid < x:
            left = mid + 1
        else:
            return mid
    return right

···

[wwz223]

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let left = 0, right = x;
  // 左闭右闭区间
  while (left <= right) {
    let mid = left + ((right - left) >> 1)
    if (mid * mid < x) {
      left = mid + 1
    } else right = mid - 1
  }
  return left * left > x ? left - 1 : left
};

[smallppgirl]

思路 二分查找

代码

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        left, right = 1, x
        while left + 1 < right:
            mid = (left + right) // 2

            if mid * mid > x:
                right = mid
            elif mid * mid == x:
                return mid
            else:
                left = mid
        return left

时间 O(logN) 空间: O(1)

[CathyShang]

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l<=r:
            mid = l+(r-l)//2
            if mid**2<=x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1 
        return ans

• Time O(logx)
• Space O(1)

[zhiyuanpeng]

class Solution: def mySqrt(self, x: int) -> int: ans, l, r = 0, 0, x while l <= r: mid = (l + r) // 2 if mid 2 > x: r = mid - 1 if mid 2 <= x: ans = mid l = mid + 1 return int(ans)

[hillsonziqiu]

方法

远古记忆被唤醒, 这个好像没有在官方题解中。已知平方根永远小于等于 1/2 原值。然后遍历1~ x/2 求平方，如果大于 x 则退出循环。对应的下标对应-1就是其平方根的下取整。

代码

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 1) {
        return 1;
    }
    let res = 1;
    while(res <= x / 2) {
        res ++;
        if (res * res > x) {

            break;
        }
    }
    return res - 1;
};

复杂度分析

时间复杂度：O(log n) 空间复杂度：O(1)