欠落した最初の正数

タイトルの説明

ソートされていない整数配列を指定し、表示されていない最小の正の整数を見つけます.
例1:

  : [1,2,0]
  : 3

例2:

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

例3:

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

説明:

あなたのアルゴリズムの時間的複雑さはO(n)であり、定数レベルの空間しか使用できません.

問題を解く

題目は時間複雑度O(n),空間複雑度O(1)を要求する.元の配列でビットマップを作成するだけで、コードは以下の通りです.

public int firstMissingPositive(int[] nums) {
		if(nums==null || nums.length<1) {
			return 1;
		}
		int n = nums.length;
		//    bitmap
		//        1~n  
		//1.          1
		//2.      ：      0   n  ，     1
		//3.    ，  nums[i]，     nums[nums[i]]   （       ），n  nums[0] 
		//4.  ，       ，       0  ，  。
		boolean contains =false;
		for(int num:nums) {
			if(num == 1) {
				contains = true;
				break;
			}
		}
		if(!contains) {
			return 1;
		}
		if(n==1) {
			return 2;
		}
		
		for(int i=0;i<n;i++) {
			if(nums[i]<=0 || nums[i]>n) {
				nums[i]=1;
			}
		}
		int val=0;
		for(int i=0;i<n;i++) {
			if(nums[i] != 1) {
				val = Math.abs(nums[i]);
				if(val!=n) {
					nums[val] = -Math.abs(nums[val]);
				}else {
					nums[0] = n;
				}
			}
		}
		
		
		for(int i=1;i<n;i++) {
			if(nums[i]>0) {
				return i;
			}
		}
		if(nums[0] != n) {
			return n;
		}
		return n+1;
    }