《力扣演算法訓練提升》數組篇-打卡數組統計-【41】缺失的第一個正數
《力扣演算法訓練提升》數組篇-打卡數組統計-【41】缺失的第一個正數
數組的基本特性
數組是最簡單的數據結構。
數組是用來存儲一系列相同類型數據，數據連續存儲，一次性分配記憶體。
數組中間進行插入和刪除，每次必須搬移後面的所有數據以保持連續，時間複雜度 O(N)。
數組索引
數組通過索引支援快速訪問數據，一個長度為N的數組，它的下標從0開始到N-1結束。
數組元素可以通過數組名稱加索引進行訪問。元素的索引是放在方括弧內，跟在數組名稱的後邊。
數組擴容
數組記憶體空間是一次性分配，擴容時，申請一塊更大的記憶體空間，再將數據拷貝到新記憶體空間，時間複雜度為O(N)。
數組遍歷
for (int i = 0; i < arr.length; i++) {
// 利用arr[i]進行數組元素操作
}
數組統計
如何統計數組中元素出現次數？
如果給定的數組元素全都是非負數，那麼針對數組中元素出現個數的統計，我們可以借用額外的輔助數組來達到統計目的。
for (int i = 0; i < nums.length; i++) {
help[nums[i]]++;
}
如何快速給定元素在數組中出現的位置？左邊xx位置？右邊xx位置？
針對元素出現在數組左邊第xx位置，右邊第xx位置，依然是藉助輔助數組。
借用left[]，right[] ，分別記錄數組從左邊開始數，第幾個位置，右邊數第幾個位置；
for (int i = 0; i < nums.length; i++) {
left[nums[i]] = i;
}
for (int i = nums.length - 1; i >= 0 ; i--) {
right[nums[i]] = nums.length - 1 - i;
}
如何判斷數組元素是否重複或者缺失？
如果數組是1~n的正數，那麼可以通過修改原數組狀態來進行判斷；
第一次訪問元素，將元素反轉為負數；
第二次訪問元素，判斷元素狀態為負數，那麼此元素為重複元素；
全部狀態修改完後，遍曆數組，當判斷元素為正數時，那麼這個位置 i 就是缺失元素！
力扣【41.缺失的第一個正數】
給你一個未排序的整數數組 nums ，請你找出其中沒有出現的最小的正整數。
請你實現時間複雜度為 O(n) 並且只使用常數級別額外空間的解決方案。
具體描述
解題討論
缺失數
歸納
缺失數一定出現在 [1, N+1] 範圍內
取得數組長度為 N
第一次遍歷，將所有非正數修改為 N+1
第二次遍歷，打標記，將元素屬於 1 ~ N 範圍內的數反轉為負數
第三次遍歷，元素大於0，則缺失數為 下標 + 1
複雜度分析
時間複雜度：O(n)。遍歷 nums 需要時間 O(n)。
空間複雜度：O(1)。不計算返回結果集，所用空間是原空間。
動畫模擬
示例
public static int firstMissingPositive(int[] nums) {
// 缺失數一定出現在 [1, N+1] 範圍內
// 取得數組長度為 N
// 第一次遍歷，將所有非正數修改為 N+1
int N = nums.length;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= 0) {
nums[i] = N + 1;
}
}
// 第二次遍歷，打標記，將元素屬於 1 ~ N 範圍內的數反轉為負數
for (int n : nums) {
if (Math.abs(n) <= N) {
nums[Math.abs(n) - 1] = - Math.abs(nums[Math.abs(n) - 1]) ;
}
}
// 第三次遍歷，元素大於0，則缺失數為 下標 + 1
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
return N + 1;
}
短話長說
學演算法，不知道從哪開始？先學什麼？什麼階段該刷什麼題？
按照力扣題目類別結構化排序刷題，從低階到高階，圖解演算法(更新中…)，有興趣的童鞋，歡迎一起從小白開始零基礎刷力扣，共同進步！
回復：678，獲取已分類好的部分刷題順序，後續內容會持續更新，感興趣的小夥伴自由拿取！
另外，有關分類，求小夥伴們不要再問我最後一類的起名了，奇技淫巧是個褒義詞，意思是指新奇的技藝和作品。
力扣修鍊體系題目，題目分類及推薦刷題順序及題解
目前暫定劃分為四個階段：
演算法低階入門篇--武者鍛體
演算法中級進階篇--武皇煉心
演算法高階強化篇--武帝粹魂
演算法奇技淫巧篇--戰鬥秘典
以上分類原諒我有個修仙夢...
缺漏內容，正在努力整理中…
