LeetCode 0069. X的平方根【Go】

简介: LeetCode 0069. X的平方根【Go】

X的平方根

LeetCode69. x的平方根

题目描述

给你一个非负整数 x ,计算并返回 x算术平方根

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

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是2.82842... 由于返回类型是整数,小数部分将被舍去。

思路

题目要求

  • 求非负整数的算术平方根
  • 保留整数

算术平方根:是一个非负整数

一个数x的算术平方根一定在0~x/2,升序数组,考虑使用二分查找法找到目标元素

注意

在二分查找过程中有三种情况

  • 如果这个整数的平方等于输入整数,那么我们就找到了这个整数;
  • 如果这个整数的平方大于输入整数,那么这个整数肯定不是我们要找的那个数;
  • 如果这个整数的平方小于输入整数,那么这个整数可能是我们要找的那个数(算术平方根为小数时只保留整数)。

若算术平方根是小数,则最后一轮循环中,mid是第一个大于x/mid的值,所以在左区间寻找,执行right = mid -1,此时right < left,结束循环,right就是只保留整数的算术平方根(通过三个指针的移动理解)。

代码

Go

func mySqrt(x int) int {
  left, right := 1, x/2
  if x <= 1 {
    return x
  }
  for left <= right {
    mid := left + (right-left)>>2
    if mid == x/mid {
      return mid
    } else if mid < x/mid {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return right
}

Link

GitHub

目录
相关文章
|
12天前
|
SQL 算法 数据可视化
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
leetcode题目69:x的平方根【python】
|
16天前
|
算法 Java Go
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 69. x 的平方根(Java/C/Python3/Golang实现含注释说明,Easy)
6 1
|
8天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
12天前
|
SQL 算法 数据挖掘
LeetCode 第四题:寻找两个正序数组的中位数 【4/1000 】【python + go】
LeetCode 第四题:寻找两个正序数组的中位数 【4/1000 】【python + go】
|
16天前
|
算法 Java Go
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 392 判断子序列(Java/C/Python3/Go实现含注释说明,Easy)
16 0
|
16天前
|
存储 算法 Java
【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode112. 路径总和(Java/C/Python3/Go实现含注释说明,Easy)
10 0
|
16天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
8 0
|
16天前
|
算法 Java Go
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
13 0
|
16天前
|
算法 Java 大数据
【经典算法】LeetCode 283. 移动零(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 283. 移动零(Java/C/Python3/Go实现含注释说明,Easy)
9 0
|
16天前
|
算法 Java Go
【经典算法】LeetCode 2两数相加(Java/C/Python3/Go实现含注释说明,中等)
【经典算法】LeetCode 2两数相加(Java/C/Python3/Go实现含注释说明,中等)
12 0