Q69 Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., 
and since we want to return an integer, the decimal part will be truncated.
解题思路:

此题目实现Python中 int(math.sqrt(x)) 的功能。简单方法就是从0开始循环,找到当前数的平方不大于x的但下一个数的平方大于x的数,然后返回当前数。但是这种做法时间复杂度为O(n^(1/2)),会超时。

可以借助二分查找的思想,时间复杂度降为 O(lgn)。

Python实现:
class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0 or x == 1:  # 注意 0, 1 这两个特殊的数字
            return x
        low = 0; high = x
        while low <= high:
            mid = (low + high) // 2
            if mid ** 2 <= x < (mid + 1) ** 2:
                return mid
            elif mid ** 2 > x:
                high = mid
            else:
                low = mid
        return 0

a = 8
b = Solution()  
print(b.mySqrt(a))  # 2

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

面试必备:30 个 Java 集合面试问题及答案

Java集合框架为Java编程语言的基础,也是Java面试中很重要的一个知识点。这里,我列出了一些关于Java集合的重要问题和答案。

1422
来自专栏大眼瞪小眼

《算法之美》例题

【3.4 拓展问题】编写一个函数,给定一个链表的头指针,要求只遍历一次,将单链表中的元素顺序反转过来。

691
来自专栏面朝大海春暖花开

java泛型理解。代码更明了。

在工作中,相对于现有的项目源码的数据库操作层,无论是mybatis,hibernate或者是自己封装的baseModel层,都会使用到泛型。

842
来自专栏java达人

泛型方法

上一篇章我们出于类型安全的考虑,不建议使用原生类型,用List<?>代替使用,但是List<?>不允许添加除null以外的任何元素,因此我们需要使用泛型方法Li...

2288
来自专栏吾爱乐享

java之学习去除ArrayList集合中重复字符串元素方式

1582
来自专栏Java后端技术

Java Collection、Map集合总结

      依赖hashCode()和equals()两个方法进行保证元素唯一性,开发中使用开发工具自动生成就好。

822
来自专栏追不上乌龟的兔子

[奇怪但有用的数据结构]线段树

线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

1.1K9
来自专栏小樱的经验随笔

C++STL中set的使用策略(详解)

set的英文意思是“集合”, 集合都不陌生吧,集合的特点有唯一性,即:每一个元素只有一个,所以set可以用来“去重”操作,set还有默认的排序。  1、头文件...

2695
来自专栏用户3030674的专栏

java 集合框架(List操作)

/*list 基本操作 * * List a=new List(); * 增 * a.add(index,element);按指定位置添加,其余元素...

1191
来自专栏测试开发架构之路

总结了一些指针易出错的常见问题(四)

指针与结构体 简介:我们可以使用C的结构体来表示数据结构元素,比如链表或树的节点,指针是把这些元素联系到一起的纽带。 typedef struct _pers...

2947

扫码关注云+社区

领取腾讯云代金券