【 LeetCode 】69、x的平方根

本文主要是介绍【 LeetCode 】69、x的平方根，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

• 实现 int sqrt(int x) 函数。
• 计算并返回 x 的平方根，其中 x 是非负整数
• 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去

Math.sqrt(x)

• 使用较为取巧的办法 直接使用Math.sqrt()

var mySqrt = function (x) {// 直接调用Math.sqrt()函数return Math.floor(Math.sqrt(x))
};
const x = 8; // 2
console.log(mySqrt(x));

二分法

基本查找步骤:
例如: x = 8 [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ......x]- left = 0   right = x = 8- mid = Math.floor((left + right) / 2) = 4- 4 * 4 = 16 > 8 表示开方值在 [0 1 2 3] 区域内-	继续二分-	right = mid - 1 = 3  left = 0-	mid  = 1-	1 * 1 = 1 < 8 表示开方值在 [ 2 3 ] 区域内-	继续二分-	left = mid + 1 = 1 + 1 = 2 right = 3-	mid = 5 / 2= 2-	2 * 2 = 4 < 8- left = mid + 1 = 2 + 1 = 3 = right	- mid = 6 / 2 = 3- 3 * 3 = 9 > 8- right = mid - 1 = 3 - 1 = 2- 此时 right = 2 < left = 3 跳出whie- return right = 2

var mySqrt = function (x) {var left = 0;var mid;var right = x;while (left <= right) {// 取中间值mid = Math.floor((left + right) / 2);// 根据中间值的平方与所求x的大小进行对比 确定开方之后的元素位于中间值的左/右侧// mid取小了 开方值在mid 右侧if (mid * mid < x) {left = mid + 1;} // mid 取大了 开方值在mid左侧else if (mid * mid > x) {right = mid - 1;} // mid 就是所求的开方值else {return mid}}return right
};
const x = 8; // 2
console.log(mySqrt(x));

这篇关于【 LeetCode 】69、x的平方根的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---