返回信息流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.
这是一条镜像帖。来源：北邮人论坛 / java / #35680同步于 2014/10/28
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
分享一道leetcode的题
EMyuan
2014/10/28镜像同步21 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
【 在 EMyuan 的大作中提到: 】
: Given an unsorted integer array, find the first missing positive integer.
: For example,
: Given [1,2,0] return 3,
: ..................
题目没看懂，但是私以为找负数,希望我不要误导群众
For(i = 0;i < = n && Given[i] >= 0 ;i++）;
Return I;
7个月之前ac的代码。。我自己都看不懂了= =
public int firstMissingPositive(int[] A) {
if(A.length == 0) return 1;
int i = 0;
while(i < A.length) {
if(A[i] == i) {
i++;
} else {
if(A[i] > 0 && A[i] < A.length && A[i] != A[A[i]]) {
int tmp = A[i];
A[i] = A[tmp];
A[tmp] = tmp;
} else {
i++;
}
}
}
for(i = 1; i < A.length; i++) {
if(A[i] != i) return i;
}
return A[0] ==A.length ? A.length + 1 : A.length;
}
【 在 EMyuan 的大作中提到: 】
: Given an unsorted integer array, find the first missing positive integer.
: For example,
: Given [1,2,0] return 3,
: ...................
还是别用Java来ACM了。。。真心不好使啊。。。
真心不是，是找第一个缺少的正数。第一个有012，缺3，第二个有134，缺2
【 在 icybee 的大作中提到: 】
: 题目没看懂，但是私以为找负数,希望我不要误导群众
: For(i = 0;i < = n && Given[i] >= 0 ;i++）;
: Return I;
求教一下怎么算复杂度，我这个的复杂度是多少呀，多谢啦。
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
public class Main {
public static void main(String[] args) {
int[] a={1,1,2,4,5,8,-1,-5,3,6,6};
//找出数组所包含的正整数
List<Integer> b=new ArrayList<Integer>();
for(int i=0;i<a.length;i++){
if(a[i]>0){
b.add(a[i]);
}
}
//去重并排序
HashSet h = new HashSet(b);
b.clear();
b.addAll(h);
Collections.sort(b);
//找到第一个丢失的正整数
int j=0;
while((j<b.size())&&(b.get(j)==(j+1))){
j++;
}
System.out.println(j+1);
}
}
【 在 laoguo 的大作中提到: 】
: 7个月之前ac的代码。。我自己都看不懂了= =
: public int firstMissingPositive(int[] A) {
: if(A.length == 0) return 1;
: ...................