题目

image.png

思路

  • 遍历一次数组把大于等于1的和小于数组大小的值放到原数组对应位置，然后再遍历一次数组查当前下标是否和值对应，如果不对应那这个下标就是答案，否则遍历完都没出现那么答案就是数组长度加1。

    代码

    1.   public int firstMissingPositive(int[] nums) {
    2.       int len = nums.length;
    3.       if (len == 0) return 1;
    4.       for (int i = 0; i < len; i++) {
    5.           while (nums[i] > 0 && nums[i] < len && nums[nums[i] - 1] != nums[i]) {
    6.               int t = nums[nums[i] - 1];
    7.               nums[nums[i] - 1] = nums[i];
    8.               nums[i] = t;
    9.           }
    10.       }
    11.       for (int i = 0; i < len; i++) {
    12.           if (nums[i] - 1 != i) return i + 1;
    13.       }
    14.       return len + 1;
    15.   }
    17.   public int firstMissingPositive(int[] nums) {
    18.       //额外数组记录哪些位置有对应位置的数据存在
    19.       int[] arr = new int[nums.length];
    20.       //注意不要记录0的位置，因此0的位置要被1替代，依次替代。
    21.       for (int i = 0; i < nums.length; i++) {
    22.           if (nums[i] > 0 && nums[i] <= nums.length) arr[nums[i] - 1]++;
    23.       }
    24.       //再次从低位开始遍历查看哪些位置的元素为空，为空则返回。
    25.       for (int i = 1; i <= nums.length; i++) {
    26.           if(arr[i - 1] == 0) return i;
    27.       }
    28.       若不为空则说明缺失的是最后长度+1
    29.       return nums.length + 1;
    30.   }

    缺失的第一个正数