【LeetCode】41. First Missing Positive

问题描述

https://leetcode.com/problems/first-missing-positive/#/description

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.

问题分析

算法：首先遍历一次进行正确的排序，然后再遍历一次，第一个不在正确位置上的数就是结果

示例：

[3,4,-1,1]
3应该在[2]
4应该在[3]
1应该在[0]
遍历一次，将各个数交换到其正确的位置后得结果：
[1 -1 3 4]

再遍历一次发现，第一个不在正确位置上的正数是2，返回2

代码

Github上LeetCode代码：https://github.com/zgljl2012/leetcode-java

public class Solution {
		/**
		 * 算法：首先遍历一次进行正确的排序，然后再遍历一次，第一个不在正确位置上的数就是结果
		 * 示例：[3,4,-1,1]
		 * 3应该在[3]
		 * 4应该在[4]
		 * 1应该在[1]
		 * 遍历一次，将各个数交换到其正确的位置后得结果：
		 * [-1,1,3,4]
		 * 再遍历一次发现，第一个不在正确位置上的正数是2，返回2
		 * 
		 * @param nums
		 * @return
		 */
	    public int firstMissingPositive(int[] nums) {
	        for(int i = 0; i < nums.length; i++) {
	        	while(nums[i] <= nums.length && nums[i] > 0 && nums[nums[i] - 1] != nums[i]) {
	        		swap(nums, i, nums[i] - 1);
	        	}
	        }
	        for(int i = 0; i < nums.length; i++) {
	        	if(nums[i] != i + 1) {
	        		return i + 1;
	        	}
	        }
	        return nums.length + 1;
	    }
	    
	    public void swap(int[] nums, int i, int j) {
	    	int tmp = nums[i];
	    	nums[i] = nums[j];
	    	nums[j] = tmp;
	    }
	}