41. First Missing Positive

Question

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Algorithm

This question has a constrain that we need to solve it in place(with no extra space) and runs in O(n) time.

We could solve it by the thought of indexed heap.

An indexed heap is : there are two arrays, one is called data_array who stores the real data, the other is called index_array who stores the index of data in the data_array. We do the heapify by sorting the index_array but with the data.

The reason we are using index heap is that the file/data may be large and it cost much when handling them in memory so we only handle their index and then find them by the index.

By doing a sort, the first index of nums save 1, the second save 2 so we could find the first missing positive number by comparing there index i and the num[i].

So we go through all the elements in nums and if nums[i] is in the range from 1 to nums.length, and nums[i] != nums[nums[i] - 1], we continuous swap it until it's ok or it's negative number.

Then we go through the array nums and find the first one whose index is not equal the number saves in that index: nums[i] - 1 != i.

A interesting thing is that, in the second loop, we use nums[i] - 1 != I while in the first loop we use nums[nums[i] - 1] != nums[I]. The reason is that in the second loop, numbers are ordered and we only take the numbers to compare while in the first loop, the number we are manipulating is nums[i] rather than i.

Code

class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                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 i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}