#141 Sqrt(x)

    xiaoxiao2025-02-14  10

    题目描述:

    Implement int sqrt(int x).

    Compute and return the square root of x.

    Have you met this question in a real interview?  Yes Example

    sqrt(3) = 1

    sqrt(4) = 2

    sqrt(5) = 2

    sqrt(10) = 3

    Challenge 

    O(log(x))

    题目思路:

    一道binary search题,boundary是1~x,然后不断缩小范围,就酱。

    Mycode(AC = 11ms):

    class Solution { public: /** * @param x: An integer * @return: The sqrt of x */ int sqrt(int x) { // write your code here if (x == 0) return x; long long down = 1, upper = x; // 2, 2 while (down < upper) { long long mid = (down + upper) / 2; // 1 if (mid * mid <= x && (mid + 1) * (mid + 1) > x) { return mid; } else if (mid * mid < x) { down = mid + 1; } else { upper = mid - 1; } } return (int)down; } };

    转载请注明原文地址: https://ju.6miu.com/read-1296445.html
    最新回复(0)