关于leetcode个人解题总结:力扣之x的平方根双指针解法思路分析优化

题目形容

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

因为返回类型是整数,后果只保留 整数局部 ,小数局部将被 舍去 。

留神: 不容许应用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:

输出: x = 4
输入: 2

示例 2:

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

提醒:

  • 0 <= x <= 231 - 1

力扣原题目地址:https://leetcode.cn/problems/…

思路解法

剖析

  • 求一个数的平方根的值,由数学常识知,那么这个值,肯定是小于等于这个数的,如:
  • 0的平方根为0,等于0
  • 1的平方根为1,等于1
  • 2的平方根约为1.414,小于2
  • 3的平方根约为1.732,小于3
  • 4的平方根为2,小于4
  • ……
  • x的平方根为m,m小于等于x
  • 所以x的平方根的值,肯定是介于0和x之间的一个数

所以,咱们能够应用双指针的形式,定义两个指针,右边指针为0,左边指针为x,而后通过中位数的积,去与x的值进行判断,等于阐明间接找到了;大于x那就把右侧指针往左挪动,即减小减一;小于x那就把左侧指针往右挪动,即增大加一;

如下代码:

实现形式一(耗时略长)

var mySqrt = function (x) {
    let left = 0 // 左侧指针初始为0
    let right = x // 右侧指针初始为x自身
    while (left <= right) { // 只有left小于等于right就始终执行,直至大于才进行
            // 保留整数局部,以9为例,中位数4.5保留4即可
            let middle = Math.floor((left + right) / 2) 
            if (middle * middle == x) { // 若等于则是刚好找到
                    return middle // 刚好找到则间接返回即可
            } else if (middle * middle > x) { // 若大于超过了
                    right = right - 1 // 那就减小一些
            } else if (middle * middle < x) { // 若小于为达到
                    left = left + 1 // 那就增大一些
            }
    }
    return right // 返回指针值即为平方根(四舍五入)
};

提交截图(超出工夫限度)

写完当前,咱们间接提交LeetCode,发现:超时了!!!

实际上这种写法,对于比拟小的x的值来说,是齐全没有问题的,然而对于比拟大的值来说,运算须要很长时间。因为right = right - 1left = left + 1。一次缩小一个,这个放大范畴太慢。

因为LeetCode对于工夫有要求,所以间接给出一个正告:超出工夫限度

那么当这个测试用例X等于2147395600时,用上述的形式,须要多长时间能力运算进去呢?如下图:

所以到这里,这个题目也算是解决了,然而工夫过长,接下来须要做的就是优化,优化,优化

实现形式二(优化工夫)

既然每次right = right - 1left = left + 1放大范畴太小了,那咱们就把放大范畴扩充一些。间接right = middle - 1以及left = middle + 1即可,咱们以中位数middle为基准,这样就缩小了很多不必要的运算。

如下代码:

var mySqrt = function (x) {
    let left = 0
    let right = x
    while (left <= right) {
        let middle = Math.floor((left + right) / 2)
        if (middle * middle == x) {
            return middle
        } else if (middle * middle > x) {
            right = middle - 1 // 因为中位数右侧的数值必定是不符合要求的,罗唆间接跳过
        } else if (middle * middle < x) {
            left = middle + 1 // 同上相似
        }
    }
    return right
};

这样的话,就缩小很多不必要的运算了,这样就可能彻底的实现工作了,如下图:

提交截图(搞定啦…)

总结

咱们在LeetCode刷题的时候,一次不能间接写出答案也没事的,咱们能够先写出一个差一些的答案,而后再优化,最终解决问题。

即为:曲线救国的大略意思吧

以上就是笔者的力扣之x的平方根的解题思路

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据