本文章是??小Y學演算法??的內容，該專欄還有多篇優質內容在等待你觀看，現在點擊右上角點擊這個————🚀訂閱專欄🚀
就可以免費觀看多篇相關內容的文章啦！
- 📢前言
- 🌲原題樣例
- 🌻C#方法：二分查找
- 🌻Java 方法一：二分法
- 🌻Java 方法二：牛頓迭代
- 💬總結
- 🚀往期優質文章分享
📢前言
| 🚀 演算法題 🚀 |
- 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
- 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
- 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
- 🌲 今天是力扣演算法題持續打卡第21天🎈！
| 🚀 演算法題 🚀 |
🌲原題樣例
實作int sqrt(int x)函式，
計算并回傳 x 的平方根，其中 x 是非負整數，
由于回傳型別是整數，結果只保留整數的部分，小數部分將被舍去，
示例 1:
輸入: 4
輸出: 2
示例 2:
輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,
由于回傳型別是整數，小數部分將被舍去，
🌻C#方法：二分查找
思路決議
根據題意我們知道，最終目的就是回傳 x 的平方根
我們可以直接呼叫Sqrt方法找到平方根，但是這就不是演算法的本意啦~
所以可以使用二分法來解決這個問題
二分查找的下界為 0，上界可以粗略地設定為 x，
在二分查找的每一步中，我們只需要比較中間元素 mid 的平方與 x 的大小關系，并通過比較的結果調整上下界的范圍，
由于我們所有的運算都是整數運算，不會存在誤差
用 midx/mid 而不是 mid*midx 防止數值溢位
代碼：
public class Solution {
public int MySqrt(int x)
{
if (x == 0) return 0;
int left = 1, right = x, mid = (left+right)/2;
while(left<right&&mid!=left)
{
if(mid== x/mid)
{
return mid;
}else if(mid < x / mid)
{
left = mid;
mid = (left + right) / 2;
}
else
{
right = mid;
mid = (left + right) / 2;
}
}
return left;
}
}
執行結果
通過
執行用時：44 ms，在所有 C# 提交中擊敗了57.74%的用戶
記憶體消耗：14.7 MB，在所有 C# 提交中擊敗了1000.00%的用戶
復雜度分析
時間復雜度：O( long x)
空間復雜度：O(1)
🌻Java 方法一：二分法
思路決議
由于 x 平方根的整數部分 ans 是滿足 k^2 ≤x 的最大 k 值，因此我們可以對 k 進行二分查找，從而得到答案，
二分查找的下界為 0，上界可以粗略地設定為 x，
在二分查找的每一步中，我們只需要比較中間元素mid 的平方與 x 的大小關系，并通過比較的結果調整上下界的范圍，
由于我們所有的運算都是整數運算，不會存在誤差，因此在得到最終的答案 ans 后，也就不需要再去嘗試ans+1 了，
代碼：
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) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
執行結果
通過
執行用時：1 ms，在所有 Java 提交中擊敗了100.00%的用戶
記憶體消耗：35.3 MB，在所有 Java 提交中擊敗了92.27%的用戶
復雜度分析
時間復雜度：O( long x)
空間復雜度：O(1)
🌻Java 方法二：牛頓迭代
思路決議
這個方法是力扣官方解答，放在這給大家看看即可，我并沒有看得很明白，，，
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
double C = x, x0 = x;
while (true) {
double xi = 0.5 * (x0 + C / x0);
if (Math.abs(x0 - xi) < 1e-7) {
break;
}
x0 = xi;
}
return (int) x0;
}
}
執行結果
通過
執行用時：1 ms，在所有 Java 提交中擊敗了100.00%的用戶
記憶體消耗：35.5 MB，在所有 Java 提交中擊敗了57.42%的用戶
復雜度分析
時間復雜度：O( long x)
空間復雜度：O(1)
💬總結
- 今天是力扣演算法題打卡的第二十一天！
- 文章采用
C#和Java兩種編程語言進行解題 - 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
- 那今天的演算法題分享到此結束啦，明天再見！
🚀往期優質文章分享
- ??Unity零基礎到入門 | 游戲引擎 Unity 從0到1的 系統學習 路線【全面總結-建議收藏】！
- 🧡花一天時間做一個高質量飛機大戰游戲，過萬字Unity完整教程！漂亮學妹看了直呼666！
- 💛回憶童年和小伙伴一起玩過的經典游戲【炸彈人小游戲】制作程序+決議
- 💚通宵一晚做出來的一款類似CS的第一人稱射擊游戲Demo！原來做游戲也不是很難
- 🤍爆肝整整一個周末寫一款類似 皇室戰爭 的 即時戰斗類 游戲Demo！兩萬多字游戲制作程序+決議！
- 💙一款類似“恐龍快打”的 橫版街機格斗游戲 該如何制作？| 一起來學習 順便送原始碼【碼文不易，建議收藏學習】
- 💜【超實用技巧】| 提高寫文的質量 和 速率必學技能： Typora 圖床配置 詳細說明
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296682.html
標籤：其他