順にチェックしていく方法
まず思いついたのがこの方法です。Runtimeは30msでした。
class Solution {
public:
int mySqrt(int x) {
for (long i = 1; i <= x; i++) {
const long square = i * i;
if (square == x) {
return i;
} else if (x < square) {
return i - 1;
}
}
return 0;
}
};最初にある程度候補を絞る方法
二乗が input より小さくなるまで input / 2 を 繰り返し、算出した値から上の数で候補を探す方法です。Runtimeは3ms(約1/10)になりました。
mySqrt(int) の for 文ではラムダ式を使用してインクリメントと二乗の計算を同時に行っています。
class Solution {
public:
int mySqrt(int x) {
long sqrt = findStart(x);
long square = sqrt*sqrt;
for (; square < x; [&sqrt, &square] () mutable { sqrt++; square = sqrt*sqrt; }()) { /* NOOP */ }
return static_cast<int>(square == x ? sqrt : sqrt - 1);
}
private:
long findStart(int x) const {
if (x < 2) {
return x;
}
long mid = x/2;
for (; x < mid*mid; mid /= 2) { /* NOOP */ }
return mid;
}
};以上です！