First Missing Positive
問題簡介:給定一個未排序的整數數組,找到最小的缺失正整數
注:
1.要求時間複雜度為o(n)並且只用恆定的空間
舉例:
1:
輸入: [1,2,0]
輸出: 3
2:
輸入: [3,4,-1,1]
輸出: 2
3:
輸入: [7,8,9,11,12]
輸出: 1
解法一:
先將數組排序,當排序後的數組的最後一個元素為負或為0即缺失的為1,定義一個目標target先定義為1,遍歷數組,在遍歷過程中將數組值與目標值比較是否相等,即target從最小正整數1開始增長
複雜度分析:
時間複雜度:o(n)只遍歷一遍數組即可
空間複雜度:o(1)使用恆定的空間
小白刷題之路,請多指教— — 要麼大器晚成,要麼石沉大海