怎么制作网站教程手机,站酷网络,建设银行网站怎么取消短信服务,售房网站模板题目
69. x 的平方根 - 力扣#xff08;LeetCode#xff09;
思路
初始化搜索范围#xff1a;
对于 x 0#xff0c;直接返回 0
对于 x 0#xff0c;设置 left 1, right x
二分查找过程#xff1a;
当 left ≤ right 时循环#xff1a;
计算中点 mid le…题目
69. x 的平方根 - 力扣LeetCode
思路
初始化搜索范围
对于 x 0直接返回 0
对于 x 0设置 left 1, right x
二分查找过程
当 left ≤ right 时循环
计算中点 mid left (right - left) / 2
比较 mid 与 x/mid 的关系等价于比较 mid^2 与 x但避免溢出
如果 mid x/mid说明 mid 太大更新 right mid - 1
如果 mid x/mid说明 mid 太小更新 left mid 1
如果 mid x/mid找到精确平方根直接返回 mid
处理非完全平方数
循环结束后right 是小于等于平方根的最大整数
返回 right 作为结果
关键技巧
避免整数溢出
使用 mid x/mid 代替 mid^2 x
这种比较方式数学上等价但避免了中间结果溢出
边界处理
特殊处理 x 0 的情况
初始化 right x 而不是 x-1确保覆盖所有可能值
返回值选择
循环结束时 left right
right 指向小于等于平方根的最大整数
left 指向大于平方根的最小整数
时间和空间复杂度
时间复杂度O(log x)二分查找的标准复杂度
空间复杂度O(1)只使用常数额外空间
读者的错误写法
class Solution {
public:int mySqrt(int x) {int left 0;int right x-1;while(left right){int mid left (right-left)/2;if(mid*mid x){right mid-1;}else if(mid*mid x){left mid1;}else if(mid*mid x){return left;}}return left;}
};
初始化错误
right x-1 可能会导致问题。如果 x 0那么 right -1这是一个无效的索引。
正确的初始化应该是 right x因为平方根不会超过 x 本身。
返回值错误
当找到 mid*mid x 时你返回的是 left 而不是 mid。
应该返回 mid因为 mid 是满足条件的值。
整数溢出风险
当 x 很大时mid*mid 可能会导致整数溢出。
应该使用 mid x/mid 进行比较避免溢出。
循环结束后的返回值
循环结束后你返回 left但此时 left rightleft 指向的是第一个大于平方根的值。
应该返回 right因为 right 指向的是最后一个小于等于平方根的值。
正确写法
class Solution {
public:int mySqrt(int x) {int left 1;int right x;while(left right){int mid left (right-left)/2;if(mid x/mid){right mid-1;}else if(mid x/mid){left mid1;}else if(mid x/mid){return mid;}}return right;}
};
