69. Sqrt(x)

求一个数的平方根,取整数。8的平方根是2.

暴力法,依次遍历即可

class Solution {
public:
    int mySqrt(int x) {
        
        for(long long i=0; i<=x; i++){
            if((i*i==x) ||((i*ix))) return i;
        }
        return x;
    }
};

二分法查找。

class Solution {
public:
    int mySqrt(int x) {
        //
        long long  low=0, high=x, mid, ans;
        while(low <= high){
            mid = (low+high)/2;
            if(mid*mid==x){
                return mid;
            }else if(mid * mid > x){
               high = mid-1; 
            }else{
               low = mid+1;
               ans = mid; //如果n不等于number*number 那么取最接近number的数。
            } 
        }
        return ans;
    }
};

你可能感兴趣的