【c++leetcode】69. Sqrt(x)

問題入口

二分搜索

最困難的是能否意識到用二分搜索法解題。

算術平方根的區間在[1, x] 。代碼如下：

class Solution {
public:int mySqrt(int x) {if (x == 1 || x == 0){return x;}int64_t start = 1;int64_t end = x;while (start <= x){int64_t mid = start + (end - start) / 2;if (mid * mid  < x){if ((mid + 1) * (mid + 1) > x)return mid;start = mid + 1;}else if(mid * mid  > x){if ((mid - 1) * (mid - 1) < x)return mid - 1;end = mid - 1;}elsereturn mid;}return 0;}
};

關于時間復雜度

以中間的元素為界，如果大于中間元素，范圍限定在右半邊，如果小于中間元素，范圍限定在左半邊。假設數組元素數為n，范圍依次是 $n\rightarrow \frac{n}{2}\rightarrow \frac{n}{4}\rightarrow ...\rightarrow 1$ 。假設通過k次找到指定元素，? $\frac{n}{2^{k}} = 1, k=log_{2}n$ 。時間復雜度為O(logn)

溢出

題目要求 $0<=x<=2^{31}-1=2147483647$

#include <cstdint>
#include <iostream>int main() {int8_t a = INT8_MAX;int16_t b = INT16_MAX;int32_t c = INT32_MAX;int64_t d = INT64_MAX;std::cout << "Maximum value of int8_t: " << +a << std::endl;std::cout << "Maximum value of int16_t: " << b << std::endl;std::cout << "Maximum value of int32_t: " << c << std::endl;std::cout << "Maximum value of int64_t: " << d << std::endl;return 0;
}

假設 mid * mid(中間元素*中間元素) > 214783647，就會引發整數溢出。

所以這里設置的數據類型是int64_t

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/18531.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/18531.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/18531.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！