- 📢前言
- 🌲原題樣例：移動零
- 🌻C#方法：排序
- 🌻Java 方法：雙指標
- Java方法二：哈希表
- 💬總結
- 🚀往期優質文章分享
📢前言
| 🚀 演算法題 🚀 |
- 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
- 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
- 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
- 🌲 今天是力扣演算法題持續打卡第51天🎈！
| 🚀 演算法題 🚀 |
🌲原題樣例：移動零
給定一個陣列 nums，撰寫一個函式將所有 0 移動到陣列的末尾，同時保持非零元素的相對順序
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
必須在原陣列上操作，不能拷貝額外的陣列，
盡量減少操作次數，
🌻C#方法：排序
增加一個索引index，從0開始，當遍歷陣列的時候，如果陣列當前位置不為0，則把當前的數值賦值給陣列[index],然后index 自增1
如果當前位置不等于索引的位置（i 只能大于等于index），那么就把當前位置賦值為0，
此操作是為將陣列后面的值變為0
代碼：
public class Solution {
public void MoveZeroes(int[] nums) {
int index =0;
for(int i=0;i<nums.Length;i++){
if(nums[i]!=0){
nums[index] = nums[i];
if(i!=index){
nums[i]=0;
}
index++;
}
}
}
}
執行結果
通過
執行用時：152 ms，在所有 C# 提交中擊敗了98.73%的用戶
記憶體消耗：51.5 MB，在所有 C# 提交中擊敗了5.06%的用戶
🌻Java 方法：雙指標
思路決議
使用雙指標，左指標指向當前已經處理好的序列的尾部，右指標指向待處理序列的頭部，
右指標不斷向右移動，每次右指標指向非零數，則將左右指標對應的數交換，同時左指標右移，
注意到以下性質：
左指標左邊均為非零數；
右指標左邊直到左指標處均為零，
因此每次交換，都是將左指標的零與右指標的非零數交換，且非零數的相對順序并未改變，
代碼：
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
執行結果
通過
執行用時：2 ms，在所有 Java 提交中擊敗了21.64%的用戶
記憶體消耗：39.9 MB，在所有 Java 提交中擊敗了5.01%的用戶
復雜度分析
時間復雜度：O( n )
空間復雜度：O( 1 )
Java方法二：哈希表
我們可以直接查詢每個數是否在陣列中出現過來找出缺失的數字，如果使用哈希表，那么每一次查詢操作都是常數時間的，
我們將陣列中的所有數插入到一個集合中，這樣每次查詢操作的時間復雜度都是 O(1)的
代碼
class Solution {
public int missingNumber(int[] nums) {
Set<Integer> numSet = new HashSet<Integer>();
for (int num : nums) numSet.add(num);
int expectedNumCount = nums.length + 1;
for (int number = 0; number < expectedNumCount; number++) {
if (!numSet.contains(number)) {
return number;
}
}
return -1;
}
}
執行結果
通過
執行用時：5 ms，在所有 Java 提交中擊敗了33.30%的用戶
記憶體消耗：38.9 MB，在所有 Java 提交中擊敗了26.29%的用戶
復雜度分析
時間復雜度：O( n )
空間復雜度：O( n )
💬總結
- 今天是力扣演算法題打卡的第五十一天！
- 文章采用
C#和Java兩種編程語言進行解題 - 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
- 那今天的演算法題分享到此結束啦，明天再見！
🚀往期優質文章分享
- ??Unity零基礎到入門 | 游戲引擎 Unity 從0到1的 系統學習 路線【全面總結-建議收藏】！
- 🧡花一天時間做一個高質量飛機大戰游戲，過萬字Unity完整教程！漂亮學妹看了直呼666！
- 💛回憶童年和小伙伴一起玩過的經典游戲【炸彈人小游戲】制作程序+決議
- 💚通宵一晚做出來的一款類似CS的第一人稱射擊游戲Demo！原來做游戲也不是很難
- 🤍爆肝整整一個周末寫一款類似 皇室戰爭 的 即時戰斗類 游戲Demo！兩萬多字游戲制作程序+決議！
- 💙一款類似“恐龍快打”的 橫版街機格斗游戲 該如何制作？| 一起來學習 順便送原始碼【碼文不易，建議收藏學習】
- 💜【超實用技巧】| 提高寫文的質量 和 速率必學技能： Typora 圖床配置 詳細說明
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/310668.html
標籤：其他