自己做的网站网页错位,离职同事以公司名义做网站,网络公司seo教程,中关村手机官网首页题目描述
实现 int sqrt(int x) 函数。计算并返回 x 的平方根#xff0c;其中 x 是非负整数。由于返回类型是整数#xff0c;结果只保留整数的部分#xff0c;小数部分将被舍去。示例 1:输入: 4
输出: 2
示例 2:输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,由于返回类型…题目描述
实现 int sqrt(int x) 函数。计算并返回 x 的平方根其中 x 是非负整数。由于返回类型是整数结果只保留整数的部分小数部分将被舍去。示例 1:输入: 4
输出: 2
示例 2:输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,由于返回类型是整数小数部分将被舍去来源力扣LeetCode
链接https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。方法1二分法
思路
这个问题分两种情况
x 有整数平方根x 没有整数平方根
第 1 种就是最基本的二分法查找目标值而第 2 种可以转化成寻找最右边的满足条件的值在这个问题里这个条件就是 target 的平方小于 x (因为题目要求结果只保留整数部分)。
首先定义搜索区间为 [l, r]注意左右都是闭区间。在循环过程中如果碰到 m 平方等于 x 就可以提前返回了。如果 m 平方小于 x收缩左边界如果 m 平方大于 x收缩右边界。最后搜索区间会被缩小到只剩一个数字 n如果 n 不是 x 的整数平方根那么还剩两种情况 如果 n2x那么 n-1 就是我们想要的结果而由于 n 平方大于 x 时我们会收缩右边界此时右指针会左移刚好指向 n-1同时结束了循环最后我们返回右指针 r 即可。如果 n2x那么 n 就是我们想要的结果由于 n 平方小于 x 时左边界会收缩此时左指针右移右指针不动依然指向 n循环结束最后我们还是返回右指针 r。所以循环结束后我们直接返回右指针 r 即可。
需要特别注意一下的是 0 和 1 这两个数字不过上面的算法对这两个数字也是有效的。
复杂度
时间复杂度$O(logx)$空间复杂度$O(1)$
代码
Python Code
class Solution(object):def mySqrt(self, x)::type x: int:rtype: intl, r, m 0, x, 0while l r:m l (r - l) // 2if m ** 2 x: return melif m ** 2 x : r m - 1else: l m 1return r
