首页 > 代码库 > LeetCode: First Missing Positive 解题报告
LeetCode: First Missing Positive 解题报告
Q:
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.
寻找数组中第一个未出现的正整数，题目本身比较常见，关键在于题目要求只能使用常数额外空间。
A:
转自Annie大神的解释
http://www.cnblogs.com/AnnieKim/archive/2013/04/21/3034631.html：
虽然不能再另外开辟非常数级的额外空间，但是可以在输入数组上就地进行swap操作。
思路：交换数组元素，使得数组中第i位存放数值(i+1)。最后遍历数组，寻找第一个不符合此要求的元素，返回其下标。整个过程需要遍历两次数组，复杂度为O(n)。
下图以题目中给出的第二个例子为例，讲解操作过程。
主页君的代码：
注意的地儿是：
1. 判断是否swap时要判目标值是不是相同（会有重复情况），否则会导致死循环。
2. 如果没找到，返回数组下标+1
1 package Algorithms.array; 2 3 public class FirstMissingPositive { 4 public static void main(String[] strs) { 5 int[] in = {1,2,0}; 6 //int[] in = {3,4,-1,1}; 7 System.out.println(firstMissingPositive(in)); 8 } 9 10 public static int firstMissingPositive(int[] A) {11 if (A == null) {12 return 0;13 }14 15 int len = A.length;16 for (int i = 0; i < len; i++) {17 // 1. The number should be in the range.18 // 2. The number should be positive.19 // 注意：和将要交换的值不可以相同，否则会死循环 20 while (A[i] <= len && A[i] > 0 && A[A[i] - 1] != A[i]) {21 swap(A, i, A[i] - 1);22 }23 }24 25 for (int i = 0; i < len; i++) {26 if (A[i] != i + 1) {27 return i + 1;28 }29 }30 31 return len + 1;32 }33 34 public static void swap(int[] A, int i, int j) {35 int tmp = A[i];36 A[i] = A[j];37 A[j] = tmp;38 }39 }
Git代码链接
LeetCode: First Missing Positive 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。