First Missing Positive

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

bucket sort

public class Solution {
    public int firstMissingPositive(int[] A) {
        //Time: O(n)  Space: O(1)
        if (A == null || A.length == 0) {
            return 1;
        }
        
        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] <= A.length && A[i] != i + 1) {
                int temp = A[i];
                //if same, don't need swap
                if (A[temp - 1] == A[i]) {
                    break;
                }
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        return A.length + 1;
    }
}

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

用三个指针，分别对应小于1，等于1，大于1。这道题目的算法我们同样可以应用到quick sort里，处理有重复元素的情况。

public class Solution {
    //Time: O(n)  Space: O(1)
    public void sortColors(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int left = 0;
        int right = A.length - 1;
        int i = 0;
        while (i <= right) {
            if (A[i] == 1) {
                i++;
            } else if (A[i] == 0) {
                int temp = A[i];
                A[i] = A[left];
                A[left] = temp;
                i++;
                left++;
            } else {
                int temp = A[i];
                A[i] = A[right];
                A[right] = temp;
                right--;
            }
        }
    }
}