資訊專欄INFORMATION COLUMN
摘要：二分搜索復(fù)雜度時間因?yàn)檎麛?shù)長度有限空間思路我們知道必定存在這么兩個整數(shù)和，所以我們要做的其實(shí)就是縮小這個的范圍。代碼牛頓迭代法復(fù)雜度時間空間思路更好的解法是用數(shù)學(xué)方法，牛頓法是非常經(jīng)典的求解方程的方法。
Sqrt
二分搜索 復(fù)雜度Implement int sqrt(int x).
Compute and return the square root of x.
時間 O(1) 因?yàn)檎麛?shù)長度有限 空間 O(1)
思路我們知道必定存在這么兩個整數(shù)a和b,a^2 <= sqrt(x) <= b^2，所以我們要做的其實(shí)就是縮小這個ab的范圍。使用二分法解這題時，通過比較mid^2和x大小來確定我們在哪一個半片中搜索。
注意這題的邊界條件較多，首先high要用long型存儲，其次如果有必要的話要判斷x是否是非負(fù)數(shù)。
代碼public class Solution {
public int mySqrt(int x) {
long low = 0 , high = x / 2;
while(low <= high){
int mid = low + (high - low) / 2;
if(mid * mid < x){
low = mid + 1;
} else {
high = mid - 1;
}
}
return (int)high;
}
}
牛頓迭代法
復(fù)雜度
時間 O(1) 空間 O(1)
思路更好的解法是用數(shù)學(xué)方法，牛頓法是非常經(jīng)典的求解方程的方法。其基本公式是$$ x_{2}=x_{1}-frac{x_{1}^2-n}{2x_{1}} $$，其中x1是上次計(jì)算結(jié)果，x2是本次計(jì)算結(jié)果，當(dāng)他的誤差小于一定值時返回。初始x值可選n/2，或者神奇數(shù)0x5f37642f。
代碼public class Solution {
public int sqrt(int x) {
// 如果初始值取0x5f37642f，則會進(jìn)一步加快計(jì)算速度
double x1 = x/2.0;
double x2 = 0.0, err = x2 - x1;
while(Math.abs(err)>0.00000001){
x2 = x1 - (x1 * x1 - x) / (2 * x1);
err = x2 - x1;
x1 = x2;
}
return (int)x2;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64460.html
摘要：牛頓迭代法的原理很簡單，其實(shí)是根據(jù)在附近的值和斜率，估計(jì)和軸的交點(diǎn)，因此牛頓迭代法的公式為其實(shí)就是求切線與軸的交點(diǎn)。代碼利用牛頓法進(jìn)行的更新，比直接從開始遍歷所作的循環(huán)要少牛頓迭代法的基本原理，請參考牛頓迭代法求開平方 描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...
摘要：用數(shù)組標(biāo)記非質(zhì)數(shù)，每當(dāng)出現(xiàn)一個為，計(jì)數(shù)器加一。關(guān)于質(zhì)數(shù)有三點(diǎn)大于的質(zhì)數(shù)一定是奇數(shù)，如，，奇數(shù)中的非質(zhì)數(shù)也一定是奇數(shù)的乘積。首先，我們用從到進(jìn)行標(biāo)記。標(biāo)記完所有的合數(shù)之后，再用到之間的遍歷，所有未被標(biāo)記的質(zhì)數(shù)。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用數(shù)組fla...
摘要：代碼實(shí)現(xiàn)在控制臺打印總結(jié)本篇文章帶大家搭好環(huán)境，并體驗(yàn)了控制臺打印。輸出結(jié)果總結(jié)熟練掌握取余和整除運(yùn)算，大有作用。終止本次循環(huán)，繼續(xù)執(zhí)行下一次循環(huán)。 ?本文收錄...
摘要：用具體的參數(shù)和返回值調(diào)用一個編譯的函數(shù)，而是一個編譯的函數(shù)的包裹，調(diào)用它會返回一個可以調(diào)用的函數(shù)。如果返回值是或你要指定不同宏，是還是。返回值用于傳給數(shù)據(jù)。對庫文件的限制調(diào)用函數(shù)作為中的函數(shù)指針使用返回一個整數(shù)來表示一個函數(shù)指針。 翻譯：云荒杯傾本文是Emscripten-WebAssembly專欄系列文章之一，更多文章請查看專欄。也可以去作者的博客閱讀文章。歡迎加入Wasm和emsc...
閱讀 3709·2021-10-13 09:40
閱讀 3170·2021-10-09 09:53
閱讀 3570·2021-09-26 09:46
閱讀 1869·2021-09-08 09:36
閱讀 4262·2021-09-02 09:46
閱讀 1329·2019-08-30 15:54
閱讀 3197·2019-08-30 15:44
閱讀 1040·2019-08-30 11:06
