剑指offer-78、求平⽅根
<h2 id="题描述">题⽬描述</h2><p>给定⼀个⾮负整数 x ，计算并返回 x 的平⽅根，即实现 int sqrt(int x) 函数。</p>
<p>正数的平⽅根有两个，只输出其中的正数平⽅根。如果平⽅根不是整数，输出只保留整数的部分，⼩数部分将被舍去。</p>
<p>示例1<br>
输⼊：8<br>
返回值：2<br>
解释：8 的平⽅根是 2.82842…，由于⼩数部分将被舍去，所以返回 2</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力枚举">暴力枚举</h3>
<p>从0开始递增，找到最大的i满足i² ≤ x < (i+1)²</p>
<pre><code class="language-java">public class Solution {
public int sqrt(int x) {
// 处理边界情况
if (x < 0) return -1; // 输入非法
if (x <= 1) return x; // 0和1的平方根是自身
// 从1开始线性查找
int i = 1;
while (i <= x / i) { // 使用除法避免溢出
i++;
}
return i - 1; // i是第一个使i² > x的数，所以平方根是i-1
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(√x)，最多需要√x次循环</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数空间</li>
</ul>
<h3 id="二分查找最优解">二分查找（最优解）</h3>
<p>在范围内查找平方根，不断缩小区间，直到找到满足条件的最大整数</p>
<p>如果 $m^2$ < n, ⽽且 $（m+1）^2$>n，那么说明 m 是 n 的平⽅根。</p>
<pre><code class="language-java">public class Solution {
public int sqrt(int x) {
if (x < 0) return -1;
if (x <= 1) return x;
int left = 1;
int right = x / 2; // 优化：平方根不会超过x/2（x≥4时）
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
long square = (long) mid * mid; // 使用long防止溢出
if (square == x) {
return mid; // 找到精确平方根
} else if (square < x) {
result = mid; // 记录当前可能的结果
left = mid + 1; // 向右查找
} else {
right = mid - 1; // 向左查找
}
}
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(logn)，每次将搜索范围减半</li>
<li>空间复杂度：O(1)</li>
</ul>
<h3 id="牛顿迭代法">牛顿迭代法</h3>
<p>这就属于是使用数学方法了</p>
<p>利用切线逼近平方根，迭代公式：xₙ₊₁ = (xₙ + a/xₙ)/2，其中a是要求平方根的数</p>
<pre><code class="language-java">public class Solution {
public int sqrt(int x) {
if (x < 0) return -1;
if (x == 0) return 0;
double guess = x; // 初始猜测值
double epsilon = 1e-6; // 精度要求
// 牛顿迭代
while (Math.abs(guess * guess - x) > epsilon) {
guess = (guess + x / guess) / 2.0;
}
return (int) guess; // 向下取整
}
/**
* 整数版本：避免浮点数运算
*/
public int sqrtInt(int x) {
if (x < 0) return -1;
if (x <= 1) return x;
long r = x; // 使用long防止溢出
// 牛顿迭代的整数版本
while (r * r > x) {
r = (r + x / r) / 2;
}
return (int) r;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log x)，收敛速度极快</li>
<li><strong>空间复杂度</strong>：O(1)，常数空间</li>
</ul>
<h3 id="位运算">位运算</h3>
<p>利用二进制特性逐位确定平方根，最高位开始，逐位尝试将1变为0或保持1</p>
<pre><code class="language-java">public class Solution {
public int sqrt(int x) {
if (x < 0) return -1;
if (x <= 1) return x;
int result = 0;
int bit = 1 << 15; // 从第16位开始尝试（因为int最大值约21亿，平方根约46340）
while (bit > 0) {
int temp = result | bit; // 尝试将当前位设为1
if (temp <= x / temp) { // 等价于temp² ≤ x
result = temp; // 当前位可以设为1
}
bit >>= 1; // 移到下一位
}
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log x)，固定32次循环（对于int类型）</li>
<li><strong>空间复杂度</strong>：O(1)，常数空间</li>
</ul>
<p><strong>位运算原理解析</strong></p>
<p>为什么从第16位开始？</p>
<ul>
<li>int最大值：2³¹-1 ≈ 21亿</li>
<li>√21亿 ≈ 46340 < 2¹⁶ = 65536</li>
<li>所以只需要检查16位即可</li>
</ul>
<p>执行过程示例（x=8，二进制1000）：</p>
<pre><code class="language-text">初始: result=0, bit=1<<15=32768
bit太大，跳过...
直到bit=4: temp=4, 4²=16 > 8 → 不设置
bit=2: temp=2, 2²=4 ≤ 8 → result=2
bit=1: temp=3, 3²=9 > 8 → 不设置
返回: result=2
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19631396
頁:
[1]