• 原题链接：41. 缺失的第一个正数

---

1- 思路

手动实现哈希的方式

• 1- 遍历数组：如果当前的元素落在了 [1,N] 区间内，则 i 元素 赋值在 i-1 的位置上
  • 比如对于数字 1 落在 数组 [0] 的位置
• 2- 判断条件
  • 利用 while 加条件 ①当前元素落在了 [1,N] 内、② nums[nums[i]-1] != nums[i]
• 3- 找到所需元素
  • 利用 for 循环遍历数组
  • 如果 nums[i] != i+1 ——> 返回 i+1
  • 否则最终返回 len+1

---

2- 实现

⭐41. 缺失的第一个正数——题解思路

class Solution {public int firstMissingPositive(int[] nums) {// 1. 遍历int len = nums.length;for(int i = 0 ;i<len;i++){// 利用 while 处理交换while(nums[i]>=1 && nums[i]<= len && nums[nums[i]-1] != nums[i]){swap(nums,i,nums[i]-1);}}for(int i = 0 ; i < len;i++){if(nums[i]!=i+1){return i+1;}}return len+1;}private void swap(int[] nums,int i,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

---

3- ACM 实现

class firstMissingPositive{public static int firstMissing(int[] nums){int len = nums.length;// 1. 第一次遍历for(int i = 0 ; i < len ; i ++){while(nums[i]>=1 && nums[i] <= len && nums[nums[i]-1] != nums[i]){swap(nums,i,nums[i]-1);}}// 2. 找到结果for(int i = 0 ; i < len ; i++){if(nums[i] != i+1){return i+1;}}return len+1;}private static void swap(int[] nums,int i,int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] nums = new int[n];for(int i = 0 ; i < n;i++){nums[i] = sc.nextInt();}System.out.println("结果是"+firstMissing(nums));}
}