LeetCode實戰：缺失的第一個正數

題目英文

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

題目中文

給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。

示例1:

輸入: [1,2,0]
輸出: 3
 

示例2:

輸入: [3,4,-1,1]
輸出: 2

示例3:

輸入: [7,8,9,11,12]
輸出: 1

示例4:

輸入: [1,1]
輸出: 2

實例5:

輸入: []
輸出: 1

說明:

你的算法的時間複雜度應為O(n)，並且只能使用常數級別的空間。

算法實現

// 把數組進行一次“排序”，
// “排序”的規則是：如果這個數字 i 落在“區間範圍裡”，i 就應該放在索引為 i - 1 的位置上。
public class Solution {
 public int FirstMissingPositive(int[] nums) {
 int len = nums.Length;
 for (int i = 0; i < len; i++)
 {
 while (nums[i] != i + 1 && nums[i] <= len && nums[i] > 0 && nums[i] != nums[nums[i] - 1])
 {
 int temp = nums[i];
 nums[i] = nums[temp - 1];
 nums[temp - 1] = temp;
 }
 }
 for (int i = 0; i < len; i++)
 {
 if (nums[i] != i + 1)
 {
 return i + 1;
 }
 }
 return len + 1; //nums.Length = 0 
 }
}

實驗結果

• 狀態：通過
• 165 / 165 個通過測試用例
• 執行用時：132 ms

提交結果

相關圖文：

• LeetCode實戰：刪除鏈表的倒數第N個節點
• LeetCode實戰：合併兩個有序鏈表
• LeetCode實戰：兩兩交換鏈表中的節點
• LeetCode實戰：旋轉鏈表
• LeetCode實戰：相同的樹
• LeetCode實戰：對稱二叉樹
• LeetCode實戰：二叉樹的最大深度
• LeetCode實戰：搜索二維矩陣
• LeetCode實戰：將有序數組轉換為二叉搜索樹
• 資料分享：數學建模資料分享 -- 圖論部分
• 資料分享：數學建模資料分享 -- 神經網絡部分
• 如何利用 C# 實現 K 最鄰近算法？
• 如何利用 C# 實現 K-D Tree 結構？
• 如何利用 C# + KDTree 實現 K 最鄰近算法？
• 如何利用 C# 對神經網絡模型進行抽象？
• 如何利用 C# 實現神經網絡的感知器模型？
• 如何利用 C# 實現 Delta 學習規則？
• 如何利用 C# 實現 誤差反向傳播 學習規則？
• 如何利用 C# 爬取帶 Token 驗證的網站數據？
• 如何利用 C# 向 Access 數據庫插入大量數據？
• 如何利用 C# + Python 破解貓眼電影的反爬蟲機制？

經過8年多的發展，LSGO軟件技術團隊在「地理信息系統」、「數據統計分析」、「計算機視覺」等領域積累了豐富的研發經驗，也建立了人才培養的完備體系，由於自己準備在「量化交易」領域精進技能，如果大家對這個領域感興趣可以與我聯繫，加入我們的量化學習群一起學習探討。

在這個領域我已做了以下積累：

策略部分：

• 數字貨幣 One 的投資價值分析
• 數字資產量化中的跨市場套利策略
• 數字資產量化中的同市場套利策略
• 數字資產量化中的網格交易法
• 我們能否效仿李笑來的投資策略？
• 賺錢是剛需，如何正確的交易股票？

數據部分：

• 如何利用 C# 爬取 One 的交易數據？
• 如何利用 C# 爬取 One 持有者返利數據？
• 如何利用 C# 爬取BigOne交易所的公告？
• 如何利用 C# 爬取Gate.io交易所的公告？
• 如何利用 C# 爬取「財報說」中的股票數據？

自動化交易部分：

• 封裝BigOne API：身份驗證
• 封裝BigOne API：獲取賬戶資產
• 封裝BigOne API：訂單系統
• 封裝BigOne API：網格交易法
• 封裝BigOne API：代碼的重構
• 進一步完善自動化交易系統 01
• 進一步完善自動化交易系統 02
• 進一步完善自動化交易系統 03
• 進一步完善自動化交易系統 04
• 如何開發「股票數據分析軟件」（上）
• 如何開發「股票數據分析軟件」（中）
• 如何開發「股票數據分析軟件」（下）
• 進一步完善「股票數據分析軟件」 - 01

後臺回覆「搜搜搜」，隨機獲取電子資源！

歡迎關注，請掃描二維碼：