💡 今日習題
實現 int sqrt(int x) 函數。
計算並返回 x 的平方根，其中 x 是非負整數。
由於返回類型是整數，結果只保留整數的部分，小數部分將被捨去。
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
由於返回類型是整數，小數部分將被捨去。
如果你想好答案了
請查看解題思路和代碼實現
▼
·解題思路·
二分法，int最大開根號也就46340.9，從0~46340之間找到n，n的平方小於x，n+1的平方大於x。
·代碼實現·
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
return ans;
}
};
·算法分析·
時間複雜度：O(logn)
空間複雜度：O(1)
微信關注「字節408考研」，
免費獲取各院校計算機軟體考研信息與專業課資料！