LeetCode 41. First Missing Positive

41. First Missing Positive

Difficulty: Hard

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Solution

Language: Java

一个没有遗漏的数组是从1到n的乱序数组，依照这个思想，把范围内的数字交换到它对应的位置上，也就是数字是1到length的数字交换到0到length-1上，然后从头开始数，哪个不是在原来的位置上哪个就是遗漏的数字。

边界条件：

1. 当出现重复数字的时候，也就是发现目前遍历到的数字和本来应该交换的位置相同时（也就是同一个数字已经归位了一次），那么直接跳过
2. 第二次从头遍历时，如果遍历完也没有return，那么说明缺的是最后一个数字，也就是 length + 1

class Solution {
      public int firstMissingPositive(int[] nums) {
            if (nums == null || nums.length == 0) {
                  return 1;
           }
            int index = 0;
            while (index < nums.length) {
                  if (nums[index] <= 0 || nums[index] > nums.length || nums[index] == index + 1) {
                        index++;
                 } else if (nums[index] == nums[nums[index] - 1]) {
                        index++;
                 } else {
                        int tmp = nums[index];
                        nums[index] = nums[tmp - 1];
                        nums[tmp - 1] = tmp;
                 }
           }
            for (int i = 0; i < nums.length; i++) {
                  if (nums[i] != i + 1) {
                        return i + 1;
                 }
           }
            return nums.length + 1;
     }
}