将出现过的正数位置标记出来两种方法:1、用正负标记。2、将合法数字交换到对应的位置,不对应的即为第一个缺失的数字。
class Solution41 { // 1、将为负数的位置变为正数,可以用n+1 // 2、nums[i]<=n 情况下 将num[i]-1位置数字变为负数,标记位该位置数字已经出现过了 // 3、遍历数组 第一个非负数字位置+1 即是未出现过的最小正数 public int firstMissingPositive(int[] nums) { int n = nums.length; // 负数全变成正数 for (int i = 0; i < n; i++) { if (nums[i] <= 0) { nums[i] = n + 1; } } // 小于n的正数对应位置变成负数表示该数字已经出现过了 for (int i = 0; i < n; i++) { // i位置可能已经被更改 int x = Math.abs(nums[i]); if (x <= n) { nums[x - 1] = -Math.abs(nums[x - 1]); } } for (int i = 0; i < n; i++) { if (nums[i] > 0) { return i + 1; } } return n + 1; } } class Solution41_swap { // 1、将 num[i] 放到 num[i]-1 位置,即将 i和num[i] 位置数字互换,直到不合法。 // 注意循环条件 当num[i] == num[num[i]-1] 时,会陷入无限循环,此时应打断。 // 2、判断 遍历判断 num[i]-1 == i 如果不相等,则该位置上数字没有出现过 public int firstMissingPositive(int[] nums) { for (int i = 0; i < nums.length; i++) { while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) { swap(nums, i, nums[i] - 1); } } for (int i = 0; i < nums.length; i++) { if (nums[i] - 1 != i) { return i + 1; } } return nums.length + 1; } private void swap(int[] nums, int s1, int s2) { int temp = nums[s1]; nums[s1] = nums[s2]; nums[s2] = temp; } }