[leetcode]First Missing Positive

新博文地址：[leetcode]First Missing Positive

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.

 这是一道好题哇，我实在没想到用O(1)的空间做解，用的O(n)，后来看了网上的解答，思路的确很相似，只是人家在原数组上直接走出了修改，我则另开了空间，但是最后呈现出来的形式是一样的。

先看下我的算法：

先遍历一遍数组A，找到在[1,a.length]范围内最大的数，比如说该数字是x，则开辟x + 1个空间copy

然后第二遍扫描数组A，将[1~x]的数字都丢到新数组的下标为其本身的槽内。例如1，就丢在copy[1]中，x就丢在copy[x]中。

扫描copy数组，遇到第一个空槽，则返回槽的索引，如果没有遇到空槽，则返回x + 1。

使用空间均值在n / 2，最坏达到O(n)。

代码如下：

 

        public int firstMissingPositive(int[] a) {
            
		if(a == null || a.length == 0){
			return 1;
		}
		int max = 0;
		for(int i = 0 ; i < a.length; i++){
			if(a[i] <= a.length && a[i] > 0 && a[i] > max){
				max = a[i];
			}
		}
		int[] copy = new int[max + 1];
		for(int i = 0; i < a.length; i++){
			if(a[i] <= a.length && a[i] > 0){
				copy[a[i]] = a[i];
			}
		}
		for(int i = 1; i < copy.length; i++){
			if(copy[i] == 0){
				return i;
			}
		}
		return copy.length;
	}

 如上所说，空间复杂度不满足题中要求，因此上网找了更好的算法，这是一个非常具有借鉴意义的题目：

 

具体的算法思想可以看这里。

道理是一样的，但是略微复杂，其将每个合法数字（1 ~ a.length）都放在属于自己的槽，但是对于非法数字则不作交换处理。

具体代码如下

public int firstMissingPositive(int[] a) {
		if(a == null || a.length == 0){
			return 1;
		}
		for(int i = 0; i < a.length;){
			if(a[i] <= a.length && a[i] > 0 && a[i] != i + 1 && a[i] != a[a[i] - 1]){
				int tem = a[a[i] - 1];
				a[a[i] - 1] = a[i];
				a[i] = tem;
			}else{
				i++;
			}
		}
		for(int i = 0 ; i < a.length; i++){
			if(a[i] != i + 1){
				return i + 1;
			}
		}
		return a.length + 1;
	}

 是厉害