Java for LeetCode 041 First Missing Positive

浏览数：44 / 时间：2015年06月08日

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.

解题思路一：

刚看到题目的时候感觉无从下手，后来仔细理解题意，需要找到first missing positive integer，只需要找到第一个即可，因此我们可以开一个布尔数组，存储i是否存在，JAVA实现如下:

public int firstMissingPositive(int[] nums) {
			boolean[] num=new boolean[nums.length + 1];
	        for (int i = 0; i < nums.length; i++) 
	            if (nums[i] > 0&&nums[i] <= nums.length)
	            	num[nums[i]-1] = true;
	        for (int i = 0; i < num.length; i++)
	            if (!num[i])
	                return i+1;
	        return 0;
	    }

解题思路二：使用bool数组会有O(N)的空间复杂度，直接采用交换的方法可以避免，JAVA实现如下：

static public int firstMissingPositive(int[] nums)  {
       if(nums.length==0)
       return 1;
	        for (int i = 0; i < nums.length; ) {
	            if (nums[i] >= 0 &&nums[i] < nums.length &&nums[i] != i && nums[i] != nums[nums[i]]){
	            	int temp=nums[i];
	            	nums[i]=nums[nums[i]];
	            	nums[temp]=temp;
	            }
	            else i++;
	        }
	        for (int i = 1; i < nums.length; ++i)
	            if (nums[i] != i)
	                return i;
	        return nums[0] == nums.length ? nums.length + 1 : nums.length;
	    }

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java for LeetCode 041 First Missing Positive