關聯LeetCode題號41

本題特點

• 數組，哈希表

本題思路

1. 找缺失的最小正數，看舉例說明缺失的正數，一種情況是連續的最小的正數，一種是缺失連續但不是最小的正數
2. 驗證數組內數組是否連續，可以通過 nums[i]+1 是否存nums組成的哈希表，如果nums[i]+1 <= 0 不符合正數的條件，輕松解決，詳情看Java寫法
3. 題目要求時間復雜度O(n)并且只使用常數級別額外空間的解決方案 ，就上難度了，hah Python 數組可以直接提供包含方法，哈哈哈，但是實際上還是通過哈希，不過我是菜雞 能AC就行
4. Python寫法是好早之前寫的了，排序之后，如果當前值和下標一致說明是不缺少的，不一致為缺少，忘記當時從哪學習來的，不過時間復雜度不滿足O(n)，因為排序了

Python寫法

def firstMissingPositive(self, nums: List[int]) -> int:# 優先把重復的，小于0的值過濾掉nums = list(filter(lambda x: x>0, list(set(nums))))if len(nums) == 0:return 1# 排序nums.sort()# 值和下標值比較，一致說明不缺少，不一致說明缺少for i in range(1, len(nums)+1):if i != nums[i-1]:return i# 補充缺少的值是數組最大值+1的情況return nums[len(nums)-1]+1

Java寫法

package leetcode;import org.junit.jupiter.api.Test;import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;/*** File Description: FirstMissingPositive_41* Author:* Date: 2025/4/30 09:39*/
public class FirstMissingPositive_41 {public int firstMissingPositive(int[] nums){Map<Integer, Integer> hashmap = new HashMap<>();int res = Integer.MAX_VALUE;for (int each: nums){hashmap.put(each, hashmap.getOrDefault(each, 0)+1);}if (hashmap.containsKey(1)){for (int i = 0; i < nums.length; i++){if (hashmap.containsKey(nums[i] + 1)) continue;else {// 不包含nums[i]+1 說明該值符合缺少條件// 判斷是不是正數if (nums[i]+1 <= 0) continue;else {// 判斷是不是最小res = Math.min(res, nums[i]+1);}}}return res;}else{// 不包含1，肯定缺少的最小正整數就是1return 1;}}@Testpublic void TestFirstMissingPositive(){int[] nums = {7,8,9,11,12};int res = firstMissingPositive(nums);System.out.println(res);}
}