`
huntfor
  • 浏览: 194213 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[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;
	}

 是厉害

 

  • 大小: 15.6 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics