《力扣演算法訓練提升》數組篇-打卡數組統計-【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,獲取已分類好的部分刷題順序,後續內容會持續更新,感興趣的小夥伴自由拿取!
另外,有關分類,求小夥伴們不要再問我最後一類的起名了,奇技淫巧是個褒義詞,意思是指新奇的技藝和作品。
力扣修鍊體系題目,題目分類及推薦刷題順序及題解
目前暫定劃分為四個階段:
演算法低階入門篇--武者鍛體
演算法中級進階篇--武皇煉心
演算法高階強化篇--武帝粹魂
演算法奇技淫巧篇--戰鬥秘典
以上分類原諒我有個修仙夢...
缺漏內容,正在努力整理中…