LeetCode41. 缺失的第一个正数(java)

题目：

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例：

说明：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

代码：（Java）

• 解法一

class Solution {
	public int firstMissingPositive(int[] nums) {
	//数组为空
		if (nums == null) {
			return 0;
		}
	//数组没有元素
		if (nums.length == 0) {
			return 1;
		}
	//数组长度为1时
		if (nums.length == 1) {
			if (nums[0] == 1) {
				return (nums[0] + 1);
			} else {
				return 1;
			}
		}
	//数组排序
		Arrays.sort(nums);
	//去除数组中的非正整数
		int[] newNums = new int[0];
		boolean flag = false;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > 0) {
				flag = true;
				newNums = Arrays.copyOfRange(nums, i, nums.length);
				break;
			}
		}
		int newNumsLength = newNums.length;
		if (!flag) {
			return 1;
		}
	//去除重复的元素
		int index = 1;
		boolean flag1 = false;
		for (int i = 1, len = newNums.length; i < len; i++) {
			if (newNums[i] != newNums[i - 1]) {
				flag1 = true;
				newNums[index++] = newNums[i];
			}
		}
		if (flag1) {
			newNums = Arrays.copyOf(newNums, index);
		} else {
			newNums = Arrays.copyOf(newNums, newNumsLength);
		}
     //具体判断应该返回的最小正整数
     //如果经过 最终的数组的长度为1时
		if (newNums.length == 1) {
			if (newNums[0] == 1) {
				return (newNums[0] + 1);
			} else {
				return 1;
			}
		}
	//1不存在时
		if (newNums[0] != 1) {
			return 1;
		}
	//1存在时
		if (newNums[0] == 1) {
			for (int i = 0; i < newNums.length - 1; i++) {
				if (newNums[i] != (newNums[i + 1] - 1)) {
					return newNums[i] + 1;	//不全部连续时，间断点位置元素+1
				}
			}
			return (newNums[newNums.length - 1] + 1);	//全部连续时，结果为最后一个元素+1
		}
		return 0;
	}
}

• 解法二：

class Solution {
		public int firstMissingPositive(int[] nums) {
		if (nums == null) {
			return 0;
		}
		if (nums.length == 0) {
			return 1;
		}
		if (nums.length == 1) {
			if (nums[0] == 1) {
				return (nums[0] + 1);
			} else {
				return 1;
			}
		}
	//	排序
		Arrays.sort(nums);
	//去除重复元素
		int index = 1;
		boolean flag1 = false;
		for (int i = 1, len = nums.length; i < len; i++) {
			if (nums[i] != nums[i - 1]) {
				nums[index++] = nums[i];
				flag1 = true;
			}
		}	
		if (flag1) {
			nums = Arrays.copyOf(nums, index);
		}
	//判断是否有1	
		boolean flag = false;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] == 1) {
				flag = true;
			}
		}
		if (!flag) {
			return 1;
		}
	//数组元素连续 结果为最后一个元素+1
		boolean flag2 = false;
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i] != (nums[i + 1] - 1)) {
				flag2 = true;
			}
		}
		if (!flag2) {
			return (nums[nums.length - 1] + 1);
		}
	//数组元素不连续 结果为间断点元素+1
		int i;
		for (i = 0; i < nums.length - 1; i++) {
			if (nums[i] != (nums[i + 1] - 1)&&nums[i]>0) {
				break;
			}
		}
		return (nums[i] + 1);
	}
}

• 解法三：

将原数组遍历 元素按照元素值存放在相应下边的一个新数组中
遍历新数组 判断新数组中第一个元素为0
返回其下标就是结果

class Solution {
	public int firstMissingPositive(int[] nums) {
		if (nums == null) {
			return 0;
		}
		if (nums.length == 0) {
			return 1;
		}
		Arrays.sort(nums);
		int[] record = new int[(nums[nums.length - 1])+2];
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > 0&&record[(nums[i])]==0) {
				record[(nums[i])] = nums[i];

			}
		}
		for(int i=1;i<record.length;i++) {
			if(record[i]==0) {
				return i;
			}
		}
		return 0;
	}
}

解法三 代码解释：

• 粘贴别人代码：

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums.length == 0){
            return 1;
         }
        //第i位存放i+1的数值
        for(int i = 0; i < nums.length;i++){
            if(nums[i] > 0){//nums[i]为正数，放在i+1位置
                //假设交换的数据还是大于0且<i+1，则放在合适的位置,且数据不相等，避免死循环
                //这个while是关键，其它都是没有难度的
                while(nums[i] > 0 && nums[i] < i+1 && nums[i] != nums[nums[i] -1]){
                    int temp = nums[nums[i]-1];//交换数据
                    nums[nums[i]-1] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        //循环寻找不符合要求的数据，返回
        for(int i = 0; i < nums.length;i++){
            if(nums[i] != i+1){
                return i+1;
            }
        }
        //假设都符合要求，则返回长度+1的值
		return nums.length + 1;
    }
}