【LeetCode】69. Sqrt(x)解法及び注釈
69. Sqrt(x)
Implement
Compute and return the square root of x.
【分析】
正の整数xについては、その平方根がx/2を超えることはできないことを知っています.そのため、この考え方に基づいて[0 x/2]間のすべての正の整数を遍歴し、それらの平方をxと比較することができます.前者が後者より小さい場合は、xの平方根(整数部分)を見つけることができますが、この方法はタイムアウトし、理想的な解法ではありません.「暴力」の解法だ.
「二分法」は、二分検索のように上下限low=1、high=x、mid=(low+high)/2を設定し、[1 x]区間で折り返し検索を行い、log(2 n)の時間的複雑度で問題を解決できるようにしていますが、midがxの平方根であるか否かを判断する際にオーバーフロー(親測定でオーバーフロー!例えばx=INT_MAX)を防止するために、必ず細部に注意してください.乗算の代わりに除算:x/mid>=mid&&&x/(mid+1)<(mid+1)、mid*mid>=x&&(mid+1)*(mid+1)【解法及び注釈】
Implement
int sqrt(int x) . Compute and return the square root of x.
【分析】
正の整数xについては、その平方根がx/2を超えることはできないことを知っています.そのため、この考え方に基づいて[0 x/2]間のすべての正の整数を遍歴し、それらの平方をxと比較することができます.前者が後者より小さい場合は、xの平方根(整数部分)を見つけることができますが、この方法はタイムアウトし、理想的な解法ではありません.「暴力」の解法だ.
「二分法」は、二分検索のように上下限low=1、high=x、mid=(low+high)/2を設定し、[1 x]区間で折り返し検索を行い、log(2 n)の時間的複雑度で問題を解決できるようにしていますが、midがxの平方根であるか否かを判断する際にオーバーフロー(親測定でオーバーフロー!例えばx=INT_MAX)を防止するために、必ず細部に注意してください.乗算の代わりに除算:x/mid>=mid&&&x/(mid+1)<(mid+1)、mid*mid>=x&&(mid+1)*(mid+1)
class Solution {
public:
int mySqrt(int x) {
//
if(x<0)return -1;
if(x==0) return 0;
//
int low=1;
int high=x;
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(x/mid>=mid&&x/(mid+1)<mid+1)return mid;//
else if(x/mid>mid)
{
low=mid+1;
}
else
{
high=mid-1;
}
}
return -1;
}
};