Sqrt(x) - LintCode
5435 ワード
examination questions
Implement int
sqrt(int x) . Compute and return the square root of x.
Example
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(10) = 3
Challenge
O(log(x))
解題コード
class Solution {
public:
/**
* @param x: An integer
* @return: The sqrt of x
*/
int sqrt(int x) {
if (x == 1){
return 1;
}
long long int temp = x / 2;
int deposit;
while (true){
if (temp * temp > x){
deposit = temp;
temp = temp / 2;
}
else{
if ((temp + 1)*(temp + 1) > x){
return temp;
}
else{
temp = (deposit + temp) / 2;
}
}
}
}
};アルゴリズム解析
二分法を用いて、1つの要求数を与え、それから半分に分け、その数の二乗が所定の数より大きい場合、その数を平分し、平分後の二乗が所定の数より小さい場合、その数と平分前の数の中数を取って二乗し、毎回二乗後にその数が所定の数より大きい場合、その数の1より小さい数の二乗が所定の数より小さいかどうかを検出し、もしそうであれば、その数は結果である.
コード解析
class Solution {
public:
/**
* @param x: An integer
* @return: The sqrt of x
*/
int sqrt(int x) {
if (x == 1){ // 1，
return 1;
}
long long int temp = x / 2; //
int deposit; // ，
while (true){
if (temp * temp > x){ //
deposit = temp; //
temp = temp / 2; //
}
else{
if ((temp + 1)*(temp + 1) > x){ // +1 x ，
return temp;
}
else{
temp = (deposit + temp) / 2; //
}
}
}
}
};