本文主要是介绍模块三:二分——69.x的平方根,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 题目描述
- 算法原理
- 解法一:暴力查找
- 解法二:二分查找
- 代码实现
- 暴力查找
- C++
- Java
题目描述
题目链接:69.x的平方根
算法原理
解法一:暴力查找
依次枚举 [0, x] 之间的所有数 i (这⾥没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回了,往后的情况就不会再判断。反⽽研究枚举区间,既耽误时间,⼜可能出错)
- 如果 i * i == x ,直接返回 x ;
- 如果 i * i > x ,说明之前的⼀个数是结果,返回 i - 1 。
由于 i * i 可能超过 int 的最⼤值,因此使⽤ long long 类型
解法二:二分查找
设 x 的平⽅根的最终结果为 index ,分析 index 左右两边区间数据的特点:
- [0, index] 之间的元素,平⽅之后都是⼩于等于 x 的;
- [index + 1, x] 之间的元素,平⽅之后都是⼤于 x 的。
因此可以使⽤⼆分查找算法。
代码实现
暴力查找
class Solution {
public:int mySqrt(int x) {// 由于两个较⼤的数相乘可能会超过 int 最⼤范围// 因此⽤ long longlong long i = 0;for (i = 0; i <= x; i++) {// 如果两个数相乘正好等于 x,直接返回 iif (i * i == x)return i;// 如果第⼀次出现两个数相乘⼤于 x,说明结果是前⼀个数if (i * i > x)return i - 1;}// 为了处理oj题需要控制所有路径都有返回值return -1;}
};
C++
class Solution {
public:int mySqrt(int x) {// 处理边界情况if (x < 1)return 0;// 二段性使用二分int left = 1, right = x;while (left < right) {// 防溢出long long mid = left + (right - left + 1) / 2;if (mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};
Java
class Solution {public int mySqrt(int x) {// 细节if (x < 1)return 0;long left = 1, right = x;while (left < right) {long mid = left + (right - left + 1) / 2;if (mid * mid <= x)left = mid;elseright = mid - 1;}return (int) left;}
}
这篇关于模块三:二分——69.x的平方根的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!