logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
昨晚又闹失眠。终于治愈了哈哈。 (转载)
avatar
昨晚又闹失眠。终于治愈了哈哈。 (转载)# Joke - 肚皮舞运动
d*o
1 楼
这道题谁能解出来？（注意，这道题题意请理解清楚）
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.
and [-3,-4,1,2,6,7] return 3
Your algorithm should run in O(n) time and uses constant space.
avatar
S*l
2 楼
多谢指教。木板干净些？
家里有小孩。
avatar
d*2
3 楼
【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 昨晚又闹失眠。终于治愈了哈哈。
发信站: BBS 未名空间站 (Fri Feb 3 16:32:43 2012, 美东)
把这段话反复看了7。8 遍，酣然入睡。一觉到天明。哈哈。
Aristotle shared Plato's view of multiple souls, (ψυχή psychí) and
further elaborated a hierarchical arrangement, corresponding to the
distinctive functions of plants, animals and people: a nutritive soul of
growth and metabolism, that all three share, a perceptive soul of pain,
pleasure and desire, that only animals and people share, and the faculty of
reason, that is unique to people only. In this view, a soul is the
hylomorphic form of a viable organism, wherein each level of the hierarchy
formally supervenes upon the substance of the preceding level. Thus, for
Aristotle, all three souls perish when the living organism dies.[3][4] For
Plato however, the soul was not dependent on the physical body, he believed
in metempsychosis, the migration of the soul to a new physical body.[5]
Dualism is closely associated with the philosophy of René Descartes (1641),
which holds that the mind is a nonphysical substance. Descartes clearly
identified the mind with consciousness and self-awareness and distinguished
this from the brain as the seat of intelligence.[6] Hence, he was the first
to formulate the mind–body problem in the form in which it exists today.[7]
Dualism is contrasted with various kinds of monism, including phenomenalism
. Substance dualism is contrasted with all forms of materialism, but
property dualism may be considered a form of emergent materialism or non-
reductive physicalism in some sense. This article discusses the various
forms of dualism and the arguments which have been made both for and against
this thesis.
avatar
m*t
5 楼
木地板。
楼梯是最容易脏，又是最难清洗的地方，如果让我再弄一次我的房子，一定上木地板。
厨房卫生间一律上tile。

【在 S**********l 的大作中提到】
: 多谢指教。木板干净些？
: 家里有小孩。
avatar
M*n
6 楼
J点？很正常的文章啊

and
of

【在 d**********2 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: 昨晚又闹失眠。终于治愈了哈哈。
: 发信站: BBS 未名空间站 (Fri Feb 3 16:32:43 2012, 美东)
: 把这段话反复看了7。8 遍，酣然入睡。一觉到天明。哈哈。
: Aristotle shared Plato's view of multiple souls, (ψυχή psychí) and
: further elaborated a hierarchical arrangement, corresponding to the
: distinctive functions of plants, animals and people: a nutritive soul of
: growth and metabolism, that all three share, a perceptive soul of pain,
: pleasure and desire, that only animals and people share, and the faculty of
avatar
b*d
7 楼
public static int findFirstMissPositive(int[] a)
{
Arrays.sort(a);
int i=0;
while(i{
if(a[i]<=0)
{
i++;
}
else
{
if(i+1{
i++;
}
else
{
break;
}
}
}
return a[i]+1;
}
欢迎拍砖！
avatar
N*n
8 楼
楼梯如果使地板的话是严重安全隐患, 非常容易滑， 一定要用地毯。 及时洗尘就是了

【在 m******t 的大作中提到】
: 木地板。
: 楼梯是最容易脏，又是最难清洗的地方，如果让我再弄一次我的房子，一定上木地板。
: 厨房卫生间一律上tile。
avatar
M*n
9 楼
你是在嘲笑古希腊哲学家们朴素的世界观而已么
那随便找一段地心说言论来不就行了
这跟嘲笑一个6岁小孩连微积分都不会有啥区别
事实上这段灵魂的三分法对后期的新柏拉图主义影响极大，而后又深刻地影响了整个基
督教神学，说是三位一体学说的奠基也不为过。生魂是人作为生命的基础，代表着存在
（圣父）；觉魂是人类欲望和感情的象征，代表着爱（圣灵）；才魂是人类理性和智力
的表现，代表着智慧（圣子）。当然你可以认为整个基督教就很可笑，但我以为在真正
理解别人在研究什么东西之前认定别人严肃的研究很可笑，并不是什么值得赞许的行为。

【在 d**********2 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: 昨晚又闹失眠。终于治愈了哈哈。
: 发信站: BBS 未名空间站 (Fri Feb 3 16:32:43 2012, 美东)
: 把这段话反复看了7。8 遍，酣然入睡。一觉到天明。哈哈。
: Aristotle shared Plato's view of multiple souls, (ψυχή psychí) and
: further elaborated a hierarchical arrangement, corresponding to the
: distinctive functions of plants, animals and people: a nutritive soul of
: growth and metabolism, that all three share, a perceptive soul of pain,
: pleasure and desire, that only animals and people share, and the faculty of
avatar
h*e
10 楼
第一行做了排序，复杂度就变成O(nlogn)了。

【在 b***d 的大作中提到】
: public static int findFirstMissPositive(int[] a)
: {
: Arrays.sort(a);
: int i=0;
: while(i: {
: if(a[i]<=0)
: {
: i++;
: }
avatar
t*z
11 楼
地板楼梯很滑，我家就是地板的楼梯，穿着拖鞋或者防滑的袜子还好些，如果普通的袜
子的话大人都容易打滑。所以我儿子3岁多能自己下楼了，，但是我还是看着提心吊胆
的。
avatar
d*2
12 楼
您是高人，这个笑点免疫了，没有别的意思。

【在 M******n 的大作中提到】
: 你是在嘲笑古希腊哲学家们朴素的世界观而已么
: 那随便找一段地心说言论来不就行了
: 这跟嘲笑一个6岁小孩连微积分都不会有啥区别
: 事实上这段灵魂的三分法对后期的新柏拉图主义影响极大，而后又深刻地影响了整个基
: 督教神学，说是三位一体学说的奠基也不为过。生魂是人作为生命的基础，代表着存在
: （圣父）；觉魂是人类欲望和感情的象征，代表着爱（圣灵）；才魂是人类理性和智力
: 的表现，代表着智慧（圣子）。当然你可以认为整个基督教就很可笑，但我以为在真正
: 理解别人在研究什么东西之前认定别人严肃的研究很可笑，并不是什么值得赞许的行为。
avatar
c*p
13 楼
换换换换换

【在 h****e 的大作中提到】
: 这道题在LeetCode上有的，叫做First Missing Positive
: http://www.leetcode.com/onlinejudge
: 没做出来，但是网上可以找到解法的。
avatar
S*l
14 楼
谢谢，怕的就是这个。地毯是不是过几年可以换一次？就是怕脏啊。

【在 t***z 的大作中提到】
: 地板楼梯很滑，我家就是地板的楼梯，穿着拖鞋或者防滑的袜子还好些，如果普通的袜
: 子的话大人都容易打滑。所以我儿子3岁多能自己下楼了，，但是我还是看着提心吊胆
: 的。
avatar
s*i
15 楼
1.只考虑数组里的元素都>1的情况，因为其它任何数组可以在O(N)的复杂度内变成>1的
情况（用0做pivot把数组划开，<=0的部分不考虑）。
2.假设现在有数组A[1..N]，且A[i]>1，那么有个“不”符合题目要求的线性算法：
设bool B[1..N]，B[i]表示i在A[1..N]里出现过了，显然B数组线性时间就能算完。
但是它不符合题目中说的常数的额外空间。
3.我们想一下如何能把A和B只用A就表示了？
可以这样：因为A[i]>1，当我们在A[i]里看到一个元素j时，如果j>N就不用管，否则就
把A[j]里的数字变成负数。这样就可以用负号来代替那个B数组。
整个时间复杂度还是线性的，并且额外的空间是常数的。
avatar
m*t
16 楼
地板滑可以夹地毯。地毯脏不是洗尘而是要洗的，可是洗地毯的机器都太沉太大，很难
用到楼梯上 。

【在 N********n 的大作中提到】
: 楼梯如果使地板的话是严重安全隐患, 非常容易滑， 一定要用地毯。 及时洗尘就是了
avatar
l*8
17 楼
int firstMissingPositive(int A[], int n) {
for (int i=0; iwhile (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
swap(A[i], A[A[i]-1]);
for (int i=0; iif(A[i] != i+1)
return i+1;
return n+1;
}
avatar
S*l
18 楼
怎么加地毯？

【在 m******t 的大作中提到】
: 地板滑可以夹地毯。地毯脏不是洗尘而是要洗的，可是洗地毯的机器都太沉太大，很难
: 用到楼梯上 。
avatar
p*2
19 楼
mark一下。
avatar
r*n
20 楼
lowes／homedepot租一个好了，很容易洗。。。

【在 m******t 的大作中提到】
: 地板滑可以夹地毯。地毯脏不是洗尘而是要洗的，可是洗地毯的机器都太沉太大，很难
: 用到楼梯上 。
avatar
q*y
21 楼
桶排
avatar
o*y
23 楼
写了个O(n)的
int firstPositive(int[] A)
{
int i = 0;
while(i < A.length)
{
if(A[i] < A.length && A[i] > 0 && A[A[i]] != A[i])
//把正数A[i]放到第i个位置
swap(A[i], A[A[i]]);
else
i++;
}
for(i = 1; i < A.length; i++)
{
if(A[i] != i) // 第i个位置上不是正数i则返回i
return i;
}
if(A[0] == A.length) // A[0]恰好是A.length则返回下一个正整数A.length+1
return A.length+1;
else // A[0] <=0 或者 > A.length, 则返回A.length
return A.length;
}
avatar
r*k
24 楼
重新构造数组，如果当前下标的value>0 && <=数组长度,则设置a[value-1] = value
例如原数组为: -3, -4, 1, 2, 6, 7
新数组为: 1, 2, 1, 2, 6, 6
然后循环数组，找到值不等于下标+1的i(a[i]!=i+1)，返回i+1
int findFirstMissingPositive(int a[], int length)
{
int temp = 0;
int i = 0;
int value;
while (i < length)
{
if (temp > 0)
{
value = temp;
}
else
{
value = a[i];
i++;
}
if (value > 0 && value <= length)
{
if (a[value-1] == value)
{
temp = 0;
}
else
{
temp = a[value-1];
a[value-1] = value;
}
}
else
{
temp = 0;
}
}
for (i = 0; i < length; i++)
{
if (a[i] != i+1)
break;
}
return i+1;
}
avatar
l*c
25 楼
我也mark一下吧，
不知道不用sort怎么找first missing positive,
用了sort就不O n 了
avatar
p*2
26 楼

我发现我很懒的看代码。能说说思路吗？

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }
avatar
p*2
27 楼

chenpp的思路应该是对的。

【在 l****c 的大作中提到】
: 我也mark一下吧，
: 不知道不用sort怎么找first missing positive,
: 用了sort就不O n 了
avatar
w*x
28 楼

二爷, 你Facebook面的到底怎么样了??

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。
avatar
l*8
29 楼
我的思路基本和onlysunny一样。

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。
avatar
h*f
30 楼
不知道我是不是解错题，如果输入的是[11,9,7,5]，那第一个missing positive
integer= 4?
or the absolute value of the number must be between 0 and last index+1?
avatar
h*s
31 楼
1

【在 h*****f 的大作中提到】
: 不知道我是不是解错题，如果输入的是[11,9,7,5]，那第一个missing positive
: integer= 4?
: or the absolute value of the number must be between 0 and last index+1?
avatar
p*2
32 楼
我写了一个
public int firstMissingPositive(int[] A)
{
int n = A.length;
int i = 0;
int j = n - 1;
while (i <= j)
{
while (i < n && A[i] >= 1 && A[i] <= n)
i++;
while (j >= 0 && (A[j] <= 0 || A[j] > n))
j--;
if (i < j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
i++;
j--;
}
}
for (i = 0; i <= j; i++)
{
int a = Math.abs(A[i]);
if (A[a - 1] > 0)
A[a - 1] = -A[a - 1];
}
for (i = 0; i <= j; i++)
if (A[i] > 0)
break;
return i + 1;
}
avatar
p*2
33 楼

不行备，看你的了。

【在 w****x 的大作中提到】
:
: 二爷, 你Facebook面的到底怎么样了??
avatar
j*h
34 楼
public class FirstMissingPositive {
int min;//Integer.MAX_VALUE;
int max;//Integer.MIN_VALUE;

private void checkMinMax(){
if( max > 0 && min > 0 ){
if( max < min ){
int temp = min;
min = max;
max = temp;
}
if( max - min > 1 )
max = -1;
}
}

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
min = -1;
max = -1;
boolean hasOne = false;

if (A.length <= 0 )
return 1;
if(A.length == 1 && A[0] != 1)
return 1;
if(A.length == 1 && A[0] == 1)
return 2;

for (int i = 0; i < A.length; i++) {
if (A[i] <= 0)
continue;
if( A[i] == 1 )
hasOne = true;

// initialize
if( min == -1 ){
min = A[i];
checkMinMax();
continue;
}
if( max == -1 ){
max = A[i];
checkMinMax();
continue;
}

if (A[i] < min) {
max = min;
min = A[i];
checkMinMax();
}else if( A[i] > max ){
min = max;
max = A[i];
checkMinMax();
}
}
if( !hasOne )
return 1;
return max == -1 ? (min + 1) : (max + 1);
}
public static void main(String[] Args) {
int[] a = { -10,-3,-100,-1000,-239,1 };
int[] b = { 3,2 };
int[] c = { 2,2 };
int[] d = { 4, 1, 2, 3 };
FirstMissingPositive temp = new FirstMissingPositive();
System.out.println(Arrays.toString(a) + " --- "
+ temp.firstMissingPositive(a));
System.out.println(Arrays.toString(b) + " --- "
+ temp.firstMissingPositive(b));
System.out.println(Arrays.toString(c) + " --- "
+ temp.firstMissingPositive(c));
System.out.println(Arrays.toString(d) + " --- "
+ temp.firstMissingPositive(d));
}
}
avatar
H*g
35 楼
呵呵，我习惯性的用QUERY来解决，供你参考

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
y*d
36 楼
find the max, min, sum and the ought-to-be sum if there were nothing missing
pretty dummy solution though

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
c*a
37 楼
如果这个数组只miss一个元素，那这是最有效的解法了。
但如果miss多个元素，就不行了。

missing

【在 y***d 的大作中提到】
: find the max, min, sum and the ought-to-be sum if there were nothing missing
: pretty dummy solution though
avatar
z*i
38 楼
/* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i/* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i];
while(val>0 && val<=n && val!=A[val-1]){
index=val-1;
val=A[index];
A[index]=index+1;
}
}
/* find the first missing postive integer A[i] where A[i]!=i+1 */
x=0; //return 0 if no missing postive integer from 1 to n
outFile<for(i=0;ioutFile<if(A[i]!=i+1){
x=i+1;
break;
}
}
outFile<return x;
}
Complexity is O(n) in time and O(1) in space.
The main difficulty on complexity is the while loop inside the for loop for
reordering. However, since each element in the range 1..n is only reordered
only once and each other element is not reordered, so the total complexity
is still O(n).
avatar
z*i
39 楼
发现跟longway解法一样。longway解法更紧凑。

【在 z********i 的大作中提到】
: /* find the first missing postivie integer in array A with n elements
: return x if one postive integer in [1..n] is missing;
: return 0 otherwise;
: */
: int findFirstMissingPositiveInteger(int A[], int n){
: int x,i,val,index;
: /* rearrange the input array A such that
: B[i]=i+1 if i+1 exist in array A, or
: B[i]=A[i] if i+1 does not exist in array A
: where B is the array rearraged from A.
avatar
m*k
40 楼
try
new int[] {40,50,40, 10,20,30}

【在 p*****2 的大作中提到】
: 我写了一个
: public int firstMissingPositive(int[] A)
: {
: int n = A.length;
: int i = 0;
: int j = n - 1;
: while (i <= j)
: {
: while (i < n && A[i] >= 1 && A[i] <= n)
: i++;
avatar
m*k
41 楼
so won't work for [10,20,30] ?

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }
avatar
l*8
42 楼
it should return 1.

【在 m*****k 的大作中提到】
: so won't work for [10,20,30] ?
avatar
d*i
43 楼


【在 l*********8 的大作中提到】
: it should return 1.
avatar
l*8
44 楼
我经常见到空回复。 不知道是什么意思？

【在 d*****i 的大作中提到】
:
avatar
C*n
45 楼
very easy
avatar
s*5
46 楼
int FindFirstMissingPositiveInteger(int a[], int size)
{
int index = 0;
while (index < size)
{
while (a[index] != index && a[index] < size
&& a[index] >0)
{
int tmp = a[a[index]];
a[a[index]] = a[index];
a[index] = tmp;
}
++index;
}
index = 1;
while (index < size)
{
if (a[index] != index)
return index;
++index;
}
return index;
};
int main(int argc, char* argv[])
{
int fff1[] = {1,2,0};
int fff2[] = {3, 4, -1, 1};
int fff3[] = {-3, -4, 1, 2, 6, 7};
int fff4[] = { -10,-3,-100,-1000,-239,1};
int fff5[] = {40,50,40, 10,20,30};
cout << " fff1: " << FindFirstMissingPositiveInteger(fff1, sizeof(fff1)/
sizeof(int)) << endl;
cout << " fff2: " << FindFirstMissingPositiveInteger(fff2, sizeof(fff2)/
sizeof(int)) << endl;
cout << " fff3: " << FindFirstMissingPositiveInteger(fff3, sizeof(fff3)/
sizeof(int)) << endl;
cout << " fff4: " << FindFirstMissingPositiveInteger(fff4, sizeof(fff4)/
sizeof(int)) << endl;
cout << " fff5: " << FindFirstMissingPositiveInteger(fff5, sizeof(fff5)/
sizeof(int)) << endl;
return 0;
}
Result:
fff1: 3
fff2: 2
fff3: 3
fff4: 2
fff5: 1
avatar
b*a
47 楼
Can we assume that there is no duplicated elements?
that is, there is no [-3,-4,1,2,6,6,7,7]

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
g*m
48 楼
数组full的空间可以无穷大...

【在 H*******g 的大作中提到】
: 呵呵，我习惯性的用QUERY来解决，供你参考
avatar
g*m
49 楼
思路是对的，但是第一个loop扫一遍好像不够。
比如 3 4 -1 1
第一遍扫完是
-1 1 3 4
还要再来一遍，才能变成
1 -1 3 4
两遍也不够，这个扫的次数如果和n相关，就不是线性的了。

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }
avatar
g*x
50 楼
public int firstMissingPositive(int[] A) {
if (A.length == 0) return 1;

int i=0;
while (iif (A[i]>=0 && A[i]if (A[i]!=i && A[i]!=A[A[i]]) {
int temp = A[A[i]];
A[A[i]] = A[i];
A[i] = temp;
continue;
}
}
i++;
}

for (i=1; iif (i!=A[i]) return i;
}

if (A[0]==A.length) return A.length+1;

return A.length;
}

【在 g***m 的大作中提到】
: 思路是对的，但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍，才能变成
: 1 -1 3 4
: 两遍也不够，这个扫的次数如果和n相关，就不是线性的了。
avatar
t*i
51 楼
long的答案没有问题，每次swap后，i会保持原值在while loop里再检测一遍

【在 g***m 的大作中提到】
: 思路是对的，但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍，才能变成
: 1 -1 3 4
: 两遍也不够，这个扫的次数如果和n相关，就不是线性的了。
avatar
g*s
52 楼
去年这个时候讨论过一次。
avatar
b*h
53 楼
使用一个原数组一样长的数组,
找出最小正整数...
int find_least_missing(const int numbers[],const int array_length)
{
int buffer_right[array_length];
for(int i=1;i{buffer_right[i]=0;}
int min_value=-1;
for (int i=1;i{
if (min_value>0) {
if (min_value>numbers[i])
min_value=numbers[i];
}
else{
if (numbers[i]>0)
min_value=numbers[i];
}
}
if (min_value>1)
return 1;
buffer_right[0]=min_value;
int total_number=array_length;
int max_right=0;
bool flag_right=0;
for (int i=1;i{
int distances;
distances=numbers[i]-min_value;
if (distances{
if (distances>0)
{buffer_right[distances]=numbers[i];
max_right=distances;}
else
total_number--;
}
else
{total_number--;
flag_right=1;
}
}
for (int i=1;i<=max_right;i++)
{
if(buffer_right[i]==0)
return min_value+i;
}
if (flag_right)
return max_right+min_value+1;
else
return 0;
}
avatar
d*o
54 楼
这道题谁能解出来？（注意，这道题题意请理解清楚）
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.
and [-3,-4,1,2,6,7] return 3
Your algorithm should run in O(n) time and uses constant space.
avatar
b*d
56 楼
public static int findFirstMissPositive(int[] a)
{
Arrays.sort(a);
int i=0;
while(i{
if(a[i]<=0)
{
i++;
}
else
{
if(i+1{
i++;
}
else
{
break;
}
}
}
return a[i]+1;
}
欢迎拍砖！
avatar
h*e
57 楼
第一行做了排序，复杂度就变成O(nlogn)了。

【在 b***d 的大作中提到】
: public static int findFirstMissPositive(int[] a)
: {
: Arrays.sort(a);
: int i=0;
: while(i: {
: if(a[i]<=0)
: {
: i++;
: }
avatar
c*p
58 楼
换换换换换

【在 h****e 的大作中提到】
: 这道题在LeetCode上有的，叫做First Missing Positive
: http://www.leetcode.com/onlinejudge
: 没做出来，但是网上可以找到解法的。
avatar
s*i
59 楼
1.只考虑数组里的元素都>1的情况，因为其它任何数组可以在O(N)的复杂度内变成>1的
情况（用0做pivot把数组划开，<=0的部分不考虑）。
2.假设现在有数组A[1..N]，且A[i]>1，那么有个“不”符合题目要求的线性算法：
设bool B[1..N]，B[i]表示i在A[1..N]里出现过了，显然B数组线性时间就能算完。
但是它不符合题目中说的常数的额外空间。
3.我们想一下如何能把A和B只用A就表示了？
可以这样：因为A[i]>1，当我们在A[i]里看到一个元素j时，如果j>N就不用管，否则就
把A[j]里的数字变成负数。这样就可以用负号来代替那个B数组。
整个时间复杂度还是线性的，并且额外的空间是常数的。
avatar
l*8
60 楼
int firstMissingPositive(int A[], int n) {
for (int i=0; iwhile (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
swap(A[i], A[A[i]-1]);
for (int i=0; iif(A[i] != i+1)
return i+1;
return n+1;
}
avatar
p*2
61 楼
mark一下。
avatar
q*y
62 楼
桶排
avatar
r*k
63 楼
重新构造数组，如果当前下标的value>0 && <=数组长度,则设置a[value-1] = value
例如原数组为: -3, -4, 1, 2, 6, 7
新数组为: 1, 2, 1, 2, 6, 6
然后循环数组，找到值不等于下标+1的i(a[i]!=i+1)，返回i+1
int findFirstMissingPositive(int a[], int length)
{
int temp = 0;
int i = 0;
int value;
while (i < length)
{
if (temp > 0)
{
value = temp;
}
else
{
value = a[i];
i++;
}
if (value > 0 && value <= length)
{
if (a[value-1] == value)
{
temp = 0;
}
else
{
temp = a[value-1];
a[value-1] = value;
}
}
else
{
temp = 0;
}
}
for (i = 0; i < length; i++)
{
if (a[i] != i+1)
break;
}
return i+1;
}
avatar
l*c
64 楼
我也mark一下吧，
不知道不用sort怎么找first missing positive,
用了sort就不O n 了
avatar
p*2
65 楼

我发现我很懒的看代码。能说说思路吗？

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }
avatar
p*2
66 楼

chenpp的思路应该是对的。

【在 l****c 的大作中提到】
: 我也mark一下吧，
: 不知道不用sort怎么找first missing positive,
: 用了sort就不O n 了
avatar
w*x
67 楼

二爷, 你Facebook面的到底怎么样了??

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。
avatar
l*8
68 楼
我的思路基本和onlysunny一样。

【在 p*****2 的大作中提到】
:
: chenpp的思路应该是对的。
avatar
h*f
69 楼
不知道我是不是解错题，如果输入的是[11,9,7,5]，那第一个missing positive
integer= 4?
or the absolute value of the number must be between 0 and last index+1?
avatar
h*s
70 楼
1

【在 h*****f 的大作中提到】
: 不知道我是不是解错题，如果输入的是[11,9,7,5]，那第一个missing positive
: integer= 4?
: or the absolute value of the number must be between 0 and last index+1?
avatar
p*2
71 楼
我写了一个
public int firstMissingPositive(int[] A)
{
int n = A.length;
int i = 0;
int j = n - 1;
while (i <= j)
{
while (i < n && A[i] >= 1 && A[i] <= n)
i++;
while (j >= 0 && (A[j] <= 0 || A[j] > n))
j--;
if (i < j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
i++;
j--;
}
}
for (i = 0; i <= j; i++)
{
int a = Math.abs(A[i]);
if (A[a - 1] > 0)
A[a - 1] = -A[a - 1];
}
for (i = 0; i <= j; i++)
if (A[i] > 0)
break;
return i + 1;
}
avatar
p*2
72 楼

不行备，看你的了。

【在 w****x 的大作中提到】
:
: 二爷, 你Facebook面的到底怎么样了??
avatar
j*h
73 楼
public class FirstMissingPositive {
int min;//Integer.MAX_VALUE;
int max;//Integer.MIN_VALUE;

private void checkMinMax(){
if( max > 0 && min > 0 ){
if( max < min ){
int temp = min;
min = max;
max = temp;
}
if( max - min > 1 )
max = -1;
}
}

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
min = -1;
max = -1;
boolean hasOne = false;

if (A.length <= 0 )
return 1;
if(A.length == 1 && A[0] != 1)
return 1;
if(A.length == 1 && A[0] == 1)
return 2;

for (int i = 0; i < A.length; i++) {
if (A[i] <= 0)
continue;
if( A[i] == 1 )
hasOne = true;

// initialize
if( min == -1 ){
min = A[i];
checkMinMax();
continue;
}
if( max == -1 ){
max = A[i];
checkMinMax();
continue;
}

if (A[i] < min) {
max = min;
min = A[i];
checkMinMax();
}else if( A[i] > max ){
min = max;
max = A[i];
checkMinMax();
}
}
if( !hasOne )
return 1;
return max == -1 ? (min + 1) : (max + 1);
}
public static void main(String[] Args) {
int[] a = { -10,-3,-100,-1000,-239,1 };
int[] b = { 3,2 };
int[] c = { 2,2 };
int[] d = { 4, 1, 2, 3 };
FirstMissingPositive temp = new FirstMissingPositive();
System.out.println(Arrays.toString(a) + " --- "
+ temp.firstMissingPositive(a));
System.out.println(Arrays.toString(b) + " --- "
+ temp.firstMissingPositive(b));
System.out.println(Arrays.toString(c) + " --- "
+ temp.firstMissingPositive(c));
System.out.println(Arrays.toString(d) + " --- "
+ temp.firstMissingPositive(d));
}
}
avatar
H*g
74 楼
呵呵，我习惯性的用QUERY来解决，供你参考

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
y*d
75 楼
find the max, min, sum and the ought-to-be sum if there were nothing missing
pretty dummy solution though

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
c*a
76 楼
如果这个数组只miss一个元素，那这是最有效的解法了。
但如果miss多个元素，就不行了。

missing

【在 y***d 的大作中提到】
: find the max, min, sum and the ought-to-be sum if there were nothing missing
: pretty dummy solution though
avatar
z*i
77 楼
/* find the first missing postivie integer in array A with n elements
return x if one postive integer in [1..n] is missing;
return 0 otherwise;
*/
int findFirstMissingPositiveInteger(int A[], int n){
int x,i,val,index;
/* rearrange the input array A such that
B[i]=i+1 if i+1 exist in array A, or
B[i]=A[i] if i+1 does not exist in array A
where B is the array rearraged from A.
*/
for(i=0;i/* put A[i] in A[A[i]-1] if 1<=A[i]<=n && A[i]!=i+1 */
val=A[i];
while(val>0 && val<=n && val!=A[val-1]){
index=val-1;
val=A[index];
A[index]=index+1;
}
}
/* find the first missing postive integer A[i] where A[i]!=i+1 */
x=0; //return 0 if no missing postive integer from 1 to n
outFile<for(i=0;ioutFile<if(A[i]!=i+1){
x=i+1;
break;
}
}
outFile<return x;
}
Complexity is O(n) in time and O(1) in space.
The main difficulty on complexity is the while loop inside the for loop for
reordering. However, since each element in the range 1..n is only reordered
only once and each other element is not reordered, so the total complexity
is still O(n).
avatar
z*i
78 楼
发现跟longway解法一样。longway解法更紧凑。

【在 z********i 的大作中提到】
: /* find the first missing postivie integer in array A with n elements
: return x if one postive integer in [1..n] is missing;
: return 0 otherwise;
: */
: int findFirstMissingPositiveInteger(int A[], int n){
: int x,i,val,index;
: /* rearrange the input array A such that
: B[i]=i+1 if i+1 exist in array A, or
: B[i]=A[i] if i+1 does not exist in array A
: where B is the array rearraged from A.
avatar
m*k
79 楼
try
new int[] {40,50,40, 10,20,30}

【在 p*****2 的大作中提到】
: 我写了一个
: public int firstMissingPositive(int[] A)
: {
: int n = A.length;
: int i = 0;
: int j = n - 1;
: while (i <= j)
: {
: while (i < n && A[i] >= 1 && A[i] <= n)
: i++;
avatar
m*k
80 楼
so won't work for [10,20,30] ?

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }
avatar
l*8
81 楼
it should return 1.

【在 m*****k 的大作中提到】
: so won't work for [10,20,30] ?
avatar
l*8
82 楼
我经常见到空回复。 不知道是什么意思？

【在 d*****i 的大作中提到】
:
avatar
C*n
83 楼
very easy
avatar
s*5
84 楼
int FindFirstMissingPositiveInteger(int a[], int size)
{
int index = 0;
while (index < size)
{
while (a[index] != index && a[index] < size
&& a[index] >0)
{
int tmp = a[a[index]];
a[a[index]] = a[index];
a[index] = tmp;
}
++index;
}
index = 1;
while (index < size)
{
if (a[index] != index)
return index;
++index;
}
return index;
};
int main(int argc, char* argv[])
{
int fff1[] = {1,2,0};
int fff2[] = {3, 4, -1, 1};
int fff3[] = {-3, -4, 1, 2, 6, 7};
int fff4[] = { -10,-3,-100,-1000,-239,1};
int fff5[] = {40,50,40, 10,20,30};
cout << " fff1: " << FindFirstMissingPositiveInteger(fff1, sizeof(fff1)/
sizeof(int)) << endl;
cout << " fff2: " << FindFirstMissingPositiveInteger(fff2, sizeof(fff2)/
sizeof(int)) << endl;
cout << " fff3: " << FindFirstMissingPositiveInteger(fff3, sizeof(fff3)/
sizeof(int)) << endl;
cout << " fff4: " << FindFirstMissingPositiveInteger(fff4, sizeof(fff4)/
sizeof(int)) << endl;
cout << " fff5: " << FindFirstMissingPositiveInteger(fff5, sizeof(fff5)/
sizeof(int)) << endl;
return 0;
}
Result:
fff1: 3
fff2: 2
fff3: 3
fff4: 2
fff5: 1
avatar
b*a
85 楼
Can we assume that there is no duplicated elements?
that is, there is no [-3,-4,1,2,6,6,7,7]

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
g*m
86 楼
数组full的空间可以无穷大...

【在 H*******g 的大作中提到】
: 呵呵，我习惯性的用QUERY来解决，供你参考
avatar
g*m
87 楼
思路是对的，但是第一个loop扫一遍好像不够。
比如 3 4 -1 1
第一遍扫完是
-1 1 3 4
还要再来一遍，才能变成
1 -1 3 4
两遍也不够，这个扫的次数如果和n相关，就不是线性的了。

【在 l*********8 的大作中提到】
: int firstMissingPositive(int A[], int n) {
: for (int i=0; i: while (A[i] > 0 && A[i] <= n && A[i] != A[A[i]-1])
: swap(A[i], A[A[i]-1]);
: for (int i=0; i: if(A[i] != i+1)
: return i+1;
: return n+1;
: }
avatar
g*x
88 楼
public int firstMissingPositive(int[] A) {
if (A.length == 0) return 1;

int i=0;
while (iif (A[i]>=0 && A[i]if (A[i]!=i && A[i]!=A[A[i]]) {
int temp = A[A[i]];
A[A[i]] = A[i];
A[i] = temp;
continue;
}
}
i++;
}

for (i=1; iif (i!=A[i]) return i;
}

if (A[0]==A.length) return A.length+1;

return A.length;
}

【在 g***m 的大作中提到】
: 思路是对的，但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍，才能变成
: 1 -1 3 4
: 两遍也不够，这个扫的次数如果和n相关，就不是线性的了。
avatar
t*i
89 楼
long的答案没有问题，每次swap后，i会保持原值在while loop里再检测一遍

【在 g***m 的大作中提到】
: 思路是对的，但是第一个loop扫一遍好像不够。
: 比如 3 4 -1 1
: 第一遍扫完是
: -1 1 3 4
: 还要再来一遍，才能变成
: 1 -1 3 4
: 两遍也不够，这个扫的次数如果和n相关，就不是线性的了。
avatar
g*s
90 楼
去年这个时候讨论过一次。
avatar
b*h
91 楼
使用一个原数组一样长的数组,
找出最小正整数...
int find_least_missing(const int numbers[],const int array_length)
{
int buffer_right[array_length];
for(int i=1;i{buffer_right[i]=0;}
int min_value=-1;
for (int i=1;i{
if (min_value>0) {
if (min_value>numbers[i])
min_value=numbers[i];
}
else{
if (numbers[i]>0)
min_value=numbers[i];
}
}
if (min_value>1)
return 1;
buffer_right[0]=min_value;
int total_number=array_length;
int max_right=0;
bool flag_right=0;
for (int i=1;i{
int distances;
distances=numbers[i]-min_value;
if (distances{
if (distances>0)
{buffer_right[distances]=numbers[i];
max_right=distances;}
else
total_number--;
}
else
{total_number--;
flag_right=1;
}
}
for (int i=1;i<=max_right;i++)
{
if(buffer_right[i]==0)
return min_value+i;
}
if (flag_right)
return max_right+min_value+1;
else
return 0;
}
avatar
j*7
92 楼
static int findPositive(int [] input)
{
int length=input.length;
for(int i=0;i{
if(input[i]!=i+1 && input[i]<=length &&input[i]>=1)
{
int temp=input[i];
input[i]=input[input[i]-1];
input[temp-1]=temp;
}
}
for(int i=0;i{
if(input[i]!=i+1)
return i+1;
}

return length+1;
}
avatar
A*o
93 楼
O(n) time, O(n) space
int find(vector & input){
vector check;
check.resize(input.size(),0);
for(int i=0;iif(input[i]>0 && input[i]<=input.size())
check[ input[i]-1 ]=input[i];
}
for(int i=0;iif(check[i]==0)
return i+1;
}
return check.size()+1;
}
avatar
b*e
94 楼
build a min-heap in o(n).
query the min element.
query the two child ot he min element.
if the three elements not consecutive. find the missing interger already.
Otherwiese, go to the smaller child until the missing integer is found. o(
logn)
complexity = o(n) + o(logn)

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
b*e
95 楼
the agorithm using -1 mentioned by others earleir is the best.
Is the algorithm below oky? seems to me no extra space is needed though....
evyerthing can be in-place?

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)
avatar
a*e
96 楼
min-heap的building time不是o(n logn) 么？

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)
avatar
c*5
97 楼
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length == 0) {// if A is empty, that means '1' is the missing
// positive
return 1;
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
i--;//continue doing A[i]
}
}
int j = 1;
while (j <= A.length && A[j - 1] == j) {
j++;
}
return j;
}
avatar
m*g
98 楼
换换换换的思路：
假设数组S个数为n。我从1开始，S[1]如果是3，我就将它放到3的位置。即S[1]和s[3]
swap。再看s[1]的值，将其放到对应的位置。直到s[1]==1，我们看s[2]。以此类推。
我们停止的地方就是要求的值。
avatar
b*e
99 楼


【在 a******e 的大作中提到】
: min-heap的building time不是o(n logn) 么？
avatar
b*e
100 楼
build heap is O(n). see CLS
avatar
a*o
101 楼
如果s[1]一直不是1,停下来的条件是啥?

【在 m*********g 的大作中提到】
: 换换换换的思路：
: 假设数组S个数为n。我从1开始，S[1]如果是3，我就将它放到3的位置。即S[1]和s[3]
: swap。再看s[1]的值，将其放到对应的位置。直到s[1]==1，我们看s[2]。以此类推。
: 我们停止的地方就是要求的值。
avatar
m*g
102 楼
believeme是对的。用heap。
avatar
B*t
103 楼
停下来的条件是 s[1] == s[s[1]]

【在 a***o 的大作中提到】
: 如果s[1]一直不是1,停下来的条件是啥?
avatar
m*1
104 楼
能解释一下你的思路吗？？

missing

【在 c******5 的大作中提到】
: public int firstMissingPositive(int[] A) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (A.length == 0) {// if A is empty, that means '1' is the missing
: // positive
: return 1;
: }
: for (int i = 0; i < A.length; i++) {
: if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
: int temp = A[A[i] - 1];
avatar
c*5
105 楼
恩 我的思路是这样的：
不断的swap 碰到零或者负数就跳过，把正数A[i]swap到A[i]-1的位置，但要注意数组
的越界，所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap，所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4

【在 m*****1 的大作中提到】
: 能解释一下你的思路吗？？
:
: missing
avatar
t*r
106 楼
新手，欢迎大家拍砖
假设数组有n个大于0的而且不重复的整数，
(1) sum all elements, if sum=n(n+1)/2， then we know its n+1
(2) if not, compare with n/2, we will have two new arrays, one contains
elements <= n/2, one >n/2. Subtract the second one with n/2. find the sum of
first array, if sum=n'(n'+1)/2, the missing element must be in the second
array
(3) split the second one into two by comparing with n/4, and repeat again..

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
N*D
107 楼
俺也凑个热闹，贴个code
Run Status: Accepted!
Program Runtime: 564 milli secs
Progress: 156/156 test cases passed.
public class Solution {

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int length = A.length;
int i = 0;
while (i < length) {
// for pointer i, swap until the condition is broken.
while ((A[i] > 0) && (A[i] < length) && (A[i] != i+1)) {
if (A[A[i]-1] != A[i]) {
int tmp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = tmp;
} else {
break;
}
}
i++;
}

for (i = 0; i < length; i++) {
if (A[i] != i+1) {
return i+1;
}
}
return length+1;
}
}
Leetcode的test case真全啊，第一次的while loop忘记加判断碰上{1,1}就死循环了。
。。
avatar
j*7
108 楼
public int firstMissingPositive(int[] input) {
// Start typing your Java solution below
// DO NOT write main() function

int length=input.length;
for(int i=0;i{

while (input[i]!=i+1 && input[i]<=length &&input[i]>=1)
{
if(input[i]==input[input[i]-1])
break;
int temp=input[i];
input[i]=input[input[i]-1];
input[temp-1]=temp;
}
}


for(int i=0;i{
if(input[i]!=i+1)
return i+1;
}

return length+1;

}
avatar
A*o
109 楼
O(n) time, O(n) space
int find(vector & input){
vector check;
check.resize(input.size(),0);
for(int i=0;iif(input[i]>0 && input[i]<=input.size())
check[ input[i]-1 ]=input[i];
}
for(int i=0;iif(check[i]==0)
return i+1;
}
return check.size()+1;
}
avatar
b*e
110 楼
build a min-heap in o(n).
query the min element.
query the two child ot he min element.
if the three elements not consecutive. find the missing interger already.
Otherwiese, go to the smaller child until the missing integer is found. o(
logn)
complexity = o(n) + o(logn)

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
b*e
111 楼
the agorithm using -1 mentioned by others earleir is the best.
Is the algorithm below oky? seems to me no extra space is needed though....
evyerthing can be in-place?

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)
avatar
a*e
112 楼
min-heap的building time不是o(n logn) 么？

【在 b*******e 的大作中提到】
: build a min-heap in o(n).
: query the min element.
: query the two child ot he min element.
: if the three elements not consecutive. find the missing interger already.
: Otherwiese, go to the smaller child until the missing integer is found. o(
: logn)
: complexity = o(n) + o(logn)
avatar
c*5
113 楼
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length == 0) {// if A is empty, that means '1' is the missing
// positive
return 1;
}
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
int temp = A[A[i] - 1];
A[A[i] - 1] = A[i];
A[i] = temp;
i--;//continue doing A[i]
}
}
int j = 1;
while (j <= A.length && A[j - 1] == j) {
j++;
}
return j;
}
avatar
m*g
114 楼
换换换换的思路：
假设数组S个数为n。我从1开始，S[1]如果是3，我就将它放到3的位置。即S[1]和s[3]
swap。再看s[1]的值，将其放到对应的位置。直到s[1]==1，我们看s[2]。以此类推。
我们停止的地方就是要求的值。
avatar
b*e
115 楼


【在 a******e 的大作中提到】
: min-heap的building time不是o(n logn) 么？
avatar
b*e
116 楼
build heap is O(n). see CLS
avatar
a*o
117 楼
如果s[1]一直不是1,停下来的条件是啥?

【在 m*********g 的大作中提到】
: 换换换换的思路：
: 假设数组S个数为n。我从1开始，S[1]如果是3，我就将它放到3的位置。即S[1]和s[3]
: swap。再看s[1]的值，将其放到对应的位置。直到s[1]==1，我们看s[2]。以此类推。
: 我们停止的地方就是要求的值。
avatar
m*g
118 楼
believeme是对的。用heap。
avatar
B*t
119 楼
停下来的条件是 s[1] == s[s[1]]

【在 a***o 的大作中提到】
: 如果s[1]一直不是1,停下来的条件是啥?
avatar
m*1
120 楼
能解释一下你的思路吗？？

missing

【在 c******5 的大作中提到】
: public int firstMissingPositive(int[] A) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (A.length == 0) {// if A is empty, that means '1' is the missing
: // positive
: return 1;
: }
: for (int i = 0; i < A.length; i++) {
: if (A[i] > 0 && (A[i] - 1 < A.length) && A[A[i] - 1] != A[i]) {
: int temp = A[A[i] - 1];
avatar
c*5
121 楼
恩 我的思路是这样的：
不断的swap 碰到零或者负数就跳过，把正数A[i]swap到A[i]-1的位置，但要注意数组
的越界，所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap，所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4

【在 m*****1 的大作中提到】
: 能解释一下你的思路吗？？
:
: missing
avatar
t*r
122 楼
新手，欢迎大家拍砖
假设数组有n个大于0的而且不重复的整数，
(1) sum all elements, if sum=n(n+1)/2， then we know its n+1
(2) if not, compare with n/2, we will have two new arrays, one contains
elements <= n/2, one >n/2. Subtract the second one with n/2. find the sum of
first array, if sum=n'(n'+1)/2, the missing element must be in the second
array
(3) split the second one into two by comparing with n/4, and repeat again..

【在 d****o 的大作中提到】
: 这道题谁能解出来？（注意，这道题题意请理解清楚）
: 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.
: and [-3,-4,1,2,6,7] return 3
: Your algorithm should run in O(n) time and uses constant space.
avatar
N*D
123 楼
俺也凑个热闹，贴个code
Run Status: Accepted!
Program Runtime: 564 milli secs
Progress: 156/156 test cases passed.
public class Solution {

public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
int length = A.length;
int i = 0;
while (i < length) {
// for pointer i, swap until the condition is broken.
while ((A[i] > 0) && (A[i] < length) && (A[i] != i+1)) {
if (A[A[i]-1] != A[i]) {
int tmp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = tmp;
} else {
break;
}
}
i++;
}

for (i = 0; i < length; i++) {
if (A[i] != i+1) {
return i+1;
}
}
return length+1;
}
}
Leetcode的test case真全啊，第一次的while loop忘记加判断碰上{1,1}就死循环了。
。。
avatar
w*o
124 楼
我用两个指针两遍夹的方法：
public int firstMissingPositive(int[] A) {
int l = 0, r = A.length-1;
while(l <= r) {
int x = A[l];
if(x == l+1) {
l++;
continue;
}
if(x <= l || x > r+1 || A[x-1] == x) {
A[l] = A[r--];
} else {
A[l] = A[x-1];
A[x-1] = x;
}
}
return l+1;
}
avatar
o*d
125 楼
思路：
O(n)复杂度。一个长度为n的数组，缺失的第一个数一定是在[1,n+1]范围内。
把所有的数换到index对应的位置，比如把1放到A[1], 2放到A[2]...
这样做完之后 如果A[i]！=i的话 那就是i缺失了 （按上面换法，A[0]应该为n）
数字对调的判断条件中注意 1)如果i不在数组index范围内就skip 2)有duplicate的情
况下，A[i]=A[A[i]]也skip
class Solution {
public:
int firstMissingPositive(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
for(int i=0; i{
while(A[i]>=0 && A[i]{ int tmp=A[A[i]]; A[A[i]]=A[i]; A[i]=tmp;}
}
for(int i=1; iif(A[i]!=i) return i;
if(A[0]!=n) return n;
return n+1;
}
};

【在 B********t 的大作中提到】
: 停下来的条件是 s[1] == s[s[1]]
相关阅读
还有种可能将军们没讨论，就是某东早泄了 (转载)求横批 (转载)俗，假情商高的人，就要讲究策略，哈哈！故事笑喷，只给年轻人看。公司新来的保安，应该是个长寿的人被奶罩和内裤的广告攻占了屏幕图片0421魔壺倒出多種飲料，被劉謙騙了壹年末福：奔驰新款996其实不算什么吧实验老鼠里，怎么没见过黄色老鼠 (转载)再也不想喝珍珠奶茶了Trust是怎么音译成托拉斯的？构思精巧啊遇到这样的男生就嫁了吧狮子大开口史上最迷人的追男孩子方式。看穿了开始，没想到结局。笑尿了。Re: 耶稣他亲爹到底是谁？ (转载)现在分手还来得及吗？被内力所伤
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。