P166 第一个缺失的正整数

描述#

这个题目说的是，给你一个整数数组，你要找到数组中没有出现的最小正整数。

这个题目要求算法只能使用 O(n) 的时间，以及 O(1) 的辅助空间。

比如说，给你的数组是：
[2, -1, 4, 1, 8]
我们可以从最小的正整数 1 开始，检查第一个没出现在这个数组的正整数。1 和 2 都出现了，而 3 不在这个数组中，因此第一个缺失的正整数是 3。

代码#

public class AlgoCasts {

  private void swap(int[] nums, int i , int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }

  // Time: O(n), Space: O(1)
  public int firstMissingPositiveSwap(int[] nums) {
    if (nums == null || nums.length == 0) return 1;
    int n = nums.length, p = 0;
    while (p < n) {
      int num = nums[p];
      if (num >= 1 && num <= n && nums[num-1] != num) {
        swap(nums, p, num-1);
      } else ++p;
    }
    for (int i = 0; i < n; ++i)
      if (nums[i] != i+1)
        return i+1;
    return n+1;
  }

  // Time: O(n), Space: O(1)
  public int firstMissingPositiveFlipSign(int[] nums) {
    if (nums == null || nums.length == 0) return 1;
    int n = nums.length;
    for (int i = 0; i < n; ++i)
      if (nums[i] < 1)
        nums[i] = n+1;
    for (int i = 0; i < n; ++i) {
      int num = Math.abs(nums[i]);
      if (num <= n && nums[num-1] > 0) {
        nums[num-1] = -nums[num-1];
      }
    }
    for (int i = 0; i < n; ++i)
      if (nums[i] > 0)
        return i+1;
    return n+1;
  }

}