《力扣演算法訓練提升》數組篇-打卡數組統計-【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,獲取已分類好的部分刷題順序,後續內容會持續更新,感興趣的小夥伴自由拿取!

另外,有關分類,求小夥伴們不要再問我最後一類的起名了,奇技淫巧是個褒義詞,意思是指新奇的技藝和作品。

力扣修鍊體系題目,題目分類及推薦刷題順序及題解

目前暫定劃分為四個階段:

演算法低階入門篇--武者鍛體

演算法中級進階篇--武皇煉心

演算法高階強化篇--武帝粹魂

演算法奇技淫巧篇--戰鬥秘典

以上分類原諒我有個修仙夢...

缺漏內容,正在努力整理中…

掃碼關注