H*e
2 楼
O(n) time, O(1) space?
题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
V*D
3 楼
老中超市排骨都切的好好的，根本不需要再切。
【在 a******g 的大作中提到】
: 大家砍排骨用什么刀？求推荐一把能切菜砍骨头的万用菜刀！
【在 a******g 的大作中提到】
: 大家砍排骨用什么刀？求推荐一把能切菜砍骨头的万用菜刀！
c*9
4 楼
有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
i]!=i的就是
//Input Array:get first positive number that is not in the array
int getfirstpositive(int* a, int len)
{
int i=0;
while(i
int m= a[i];
if (m>=0&&m
int tmp;
tmp = a[m];
a[m] = m;
a[i] = tmp;
}
else
i++;
}
for (i=1;i
if (a[i]!=i)
{
return i;
}
}
if(a[0] == len)
return len+1;
else
return len;
}
i]!=i的就是
//Input Array:get first positive number that is not in the array
int getfirstpositive(int* a, int len)
{
int i=0;
while(i
int m= a[i];
if (m>=0&&m
int tmp;
tmp = a[m];
a[m] = m;
a[i] = tmp;
}
else
i++;
}
for (i=1;i
if (a[i]!=i)
{
return i;
}
}
if(a[0] == len)
return len+1;
else
return len;
}
V*D
5 楼
老中超市排骨都切的好好的，根本不需要再切。
【在 a******g 的大作中提到】
: 大家砍排骨用什么刀？求推荐一把能切菜砍骨头的万用菜刀！
【在 a******g 的大作中提到】
: 大家砍排骨用什么刀？求推荐一把能切菜砍骨头的万用菜刀！
s*n
6 楼
[3,4,-1,1] 下标越界
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
m*n
7 楼
OldMei 超市 too. you can ask butcher to cut into smaller for you.
i usually ask them to make into 1/3.
【在 V**D 的大作中提到】
: 老中超市排骨都切的好好的，根本不需要再切。
i usually ask them to make into 1/3.
【在 V**D 的大作中提到】
: 老中超市排骨都切的好好的，根本不需要再切。
c*9
8 楼
我试了下没有越界，因为会跳过负数
【在 s******n 的大作中提到】
: [3,4,-1,1] 下标越界
:
: a[
【在 s******n 的大作中提到】
: [3,4,-1,1] 下标越界
:
: a[
s*n
9 楼
跳过就好了
【在 c****9 的大作中提到】
: 我试了下没有越界，因为会跳过负数
【在 c****9 的大作中提到】
: 我试了下没有越界，因为会跳过负数
w*o
10 楼
如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
]==n
【在 s******n 的大作中提到】
: 跳过就好了
]==n
【在 s******n 的大作中提到】
: 跳过就好了
e*l
11 楼
[2,1,2] 死循环？
w*o
12 楼
这个不会的。
a[0]=2, a[2]=2, 所以他们不会swap
【在 e***l 的大作中提到】
: [2,1,2] 死循环？
a[0]=2, a[2]=2, 所以他们不会swap
【在 e***l 的大作中提到】
: [2,1,2] 死循环？
s*r
13 楼
那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
c*g
14 楼
用partition，然后计算个数？
但是，负数怎么处理呢？
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
但是，负数怎么处理呢？
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
c*9
15 楼
嗯，对的。确实有这个bug，已改
[0
【在 w****o 的大作中提到】
: 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
: ]==n
[0
【在 w****o 的大作中提到】
: 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
: ]==n
c*9
16 楼
不会越界，因为跳过了，不需要额外是space， 是通过判断index的得到结论的，因为n
个元素那个最小的正数肯定在0到n+1的范围。
【在 s*****r 的大作中提到】
: 那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
:
: a[
个元素那个最小的正数肯定在0到n+1的范围。
【在 s*****r 的大作中提到】
: 那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
:
: a[
R*9
17 楼
int SmallestMissingPositive(int a[], int n)
{
int i = 0;
int min = MAXINT;
while(i<=n-1){
if(a[i]<=0 || a[i]>n){
a[i] = a[n-1];
n--;
}else{
min = mini++;
}
}
return min;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
{
int i = 0;
int min = MAXINT;
while(i<=n-1){
if(a[i]<=0 || a[i]>n){
a[i] = a[n-1];
n--;
}else{
min = mini++;
}
}
return min;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
H*1
19 楼
如果是这样，[3, 4, -1, 1]会返回5
答案应该是2
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
答案应该是2
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
m*6
20 楼
O(n)?
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
G*s
21 楼
此题是 given int array in range [1,N]，find missing integer的变形吧，
in my opinion
扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
gives us O(n+k).
不知道这样做是否妥当和最有呢
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
in my opinion
扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
gives us O(n+k).
不知道这样做是否妥当和最有呢
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
g*y
23 楼
public int find(int[] a) {
int least = a.length;
for (int i=a.length-1; i>=0; i--) {
if (a[i]<=0 || a[i]>i+1) {
least = i;
continue;
}
if (a[i] != i+1) {
if (a[i] == a[a[i]-1]) {
least = i;
}
else {
int t = a[i]-1;
a[i] = a[t];
a[t] = t+1;
i++;
}
}
}
return least+1;
}
int least = a.length;
for (int i=a.length-1; i>=0; i--) {
if (a[i]<=0 || a[i]>i+1) {
least = i;
continue;
}
if (a[i] != i+1) {
if (a[i] == a[a[i]-1]) {
least = i;
}
else {
int t = a[i]-1;
a[i] = a[t];
a[t] = t+1;
i++;
}
}
}
return least+1;
}
A*u
24 楼
大牛，看不懂
可否详解
【在 g**********y 的大作中提到】
: public int find(int[] a) {
: int least = a.length;
:
: for (int i=a.length-1; i>=0; i--) {
: if (a[i]<=0 || a[i]>i+1) {
: least = i;
: continue;
: }
:
: if (a[i] != i+1) {
可否详解
【在 g**********y 的大作中提到】
: public int find(int[] a) {
: int least = a.length;
:
: for (int i=a.length-1; i>=0; i--) {
: if (a[i]<=0 || a[i]>i+1) {
: least = i;
: continue;
: }
:
: if (a[i] != i+1) {
c*2
25 楼
方法挺好的，但是好像空间不是O(1)吧
int,
【在 G**********s 的大作中提到】
: 此题是 given int array in range [1,N]，find missing integer的变形吧，
: in my opinion
: 扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
: assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
: gives us O(n+k).
: 不知道这样做是否妥当和最有呢
int,
【在 G**********s 的大作中提到】
: 此题是 given int array in range [1,N]，find missing integer的变形吧，
: in my opinion
: 扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
: assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
: gives us O(n+k).
: 不知道这样做是否妥当和最有呢
g*y
26 楼
http://www.mitbbs.com/article0/JobHunting/31902917_0.html
【在 A**u 的大作中提到】
: 大牛，看不懂
: 可否详解
【在 A**u 的大作中提到】
: 大牛，看不懂
: 可否详解
s*e
27 楼
扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
。
扫描第二遍，返回第一个小于等于0的数组index。
int findPosMissing(int* arr, int size) {
for (int i=0; i
int temp = arr[i];
arr[i] = 0;
int temp1;
while (true) {
if (temp <=0 ) break;
if (temp > size ) break;
if (arr[temp-1] == temp) break;
temp1 = arr[temp-1];
arr[temp-1]= temp;
temp = temp1;
}
}
for (int i=0; i
return i+1;
}
}
return size+1;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
。
扫描第二遍，返回第一个小于等于0的数组index。
int findPosMissing(int* arr, int size) {
for (int i=0; i
int temp = arr[i];
arr[i] = 0;
int temp1;
while (true) {
if (temp <=0 ) break;
if (temp > size ) break;
if (arr[temp-1] == temp) break;
temp1 = arr[temp-1];
arr[temp-1]= temp;
temp = temp1;
}
}
for (int i=0; i
return i+1;
}
}
return size+1;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
P*A
28 楼
if (arr[i]<=0) 有问题，没考虑arr[i]>n
应该改成 if(arr[i]!=i+1)
【在 s****e 的大作中提到】
: 扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
: 。
: 扫描第二遍，返回第一个小于等于0的数组index。
: int findPosMissing(int* arr, int size) {
: for (int i=0; i
: int temp = arr[i];
: arr[i] = 0;
: int temp1;
: while (true) {
应该改成 if(arr[i]!=i+1)
【在 s****e 的大作中提到】
: 扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
: 。
: 扫描第二遍，返回第一个小于等于0的数组index。
: int findPosMissing(int* arr, int size) {
: for (int i=0; i
: int temp = arr[i];
: arr[i] = 0;
: int temp1;
: while (true) {
i*e
29 楼
他代码没问题，这里handle了：
if (temp <=0 ) break;
if (temp > size ) break;
另外随手写了一个，基于 cx3959 的思路（除了他没有handle n==0 这个状况之外，他
这个思路是挺简洁的）：
int firstMissingPositive(int A[], int n) {
if (n == 0) return 1;
for (int i = 0; i < n; i++)
while (A[i] >= 0 && A[i] < n && A[i] != A[A[i]])
swap(A[i], A[A[i]]);
for (int i = 1; i < n; i++)
if (A[i] != i) return i;
return (A[0] == n) ? n+1 : n;
}
【在 P*A 的大作中提到】
: if (arr[i]<=0) 有问题，没考虑arr[i]>n
: 应该改成 if(arr[i]!=i+1)
if (temp <=0 ) break;
if (temp > size ) break;
另外随手写了一个，基于 cx3959 的思路（除了他没有handle n==0 这个状况之外，他
这个思路是挺简洁的）：
int firstMissingPositive(int A[], int n) {
if (n == 0) return 1;
for (int i = 0; i < n; i++)
while (A[i] >= 0 && A[i] < n && A[i] != A[A[i]])
swap(A[i], A[A[i]]);
for (int i = 1; i < n; i++)
if (A[i] != i) return i;
return (A[0] == n) ? n+1 : n;
}
【在 P*A 的大作中提到】
: if (arr[i]<=0) 有问题，没考虑arr[i]>n
: 应该改成 if(arr[i]!=i+1)
H*e
30 楼
O(n) time, O(1) space?
题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
c*9
31 楼
有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
i]!=i的就是
//Input Array:get first positive number that is not in the array
int getfirstpositive(int* a, int len)
{
int i=0;
while(i
int m= a[i];
if (m>=0&&m
int tmp;
tmp = a[m];
a[m] = m;
a[i] = tmp;
}
else
i++;
}
for (i=1;i
if (a[i]!=i)
{
return i;
}
}
if(a[0] == len)
return len+1;
else
return len;
}
i]!=i的就是
//Input Array:get first positive number that is not in the array
int getfirstpositive(int* a, int len)
{
int i=0;
while(i
int m= a[i];
if (m>=0&&m
int tmp;
tmp = a[m];
a[m] = m;
a[i] = tmp;
}
else
i++;
}
for (i=1;i
if (a[i]!=i)
{
return i;
}
}
if(a[0] == len)
return len+1;
else
return len;
}
s*n
32 楼
[3,4,-1,1] 下标越界
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
c*9
33 楼
我试了下没有越界，因为会跳过负数
【在 s******n 的大作中提到】
: [3,4,-1,1] 下标越界
:
: a[
【在 s******n 的大作中提到】
: [3,4,-1,1] 下标越界
:
: a[
s*n
34 楼
跳过就好了
【在 c****9 的大作中提到】
: 我试了下没有越界，因为会跳过负数
【在 c****9 的大作中提到】
: 我试了下没有越界，因为会跳过负数
w*o
35 楼
如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
]==n
【在 s******n 的大作中提到】
: 跳过就好了
]==n
【在 s******n 的大作中提到】
: 跳过就好了
e*l
36 楼
[2,1,2] 死循环？
w*o
37 楼
这个不会的。
a[0]=2, a[2]=2, 所以他们不会swap
【在 e***l 的大作中提到】
: [2,1,2] 死循环？
a[0]=2, a[2]=2, 所以他们不会swap
【在 e***l 的大作中提到】
: [2,1,2] 死循环？
s*r
38 楼
那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
c*g
39 楼
用partition，然后计算个数？
但是，负数怎么处理呢？
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
但是，负数怎么处理呢？
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
c*9
40 楼
嗯，对的。确实有这个bug，已改
[0
【在 w****o 的大作中提到】
: 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
: ]==n
[0
【在 w****o 的大作中提到】
: 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
: ]==n
c*9
41 楼
不会越界，因为跳过了，不需要额外是space， 是通过判断index的得到结论的，因为n
个元素那个最小的正数肯定在0到n+1的范围。
【在 s*****r 的大作中提到】
: 那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
:
: a[
个元素那个最小的正数肯定在0到n+1的范围。
【在 s*****r 的大作中提到】
: 那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
:
: a[
R*9
42 楼
int SmallestMissingPositive(int a[], int n)
{
int i = 0;
int min = MAXINT;
while(i<=n-1){
if(a[i]<=0 || a[i]>n){
a[i] = a[n-1];
n--;
}else{
min = mini++;
}
}
return min;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
{
int i = 0;
int min = MAXINT;
while(i<=n-1){
if(a[i]<=0 || a[i]>n){
a[i] = a[n-1];
n--;
}else{
min = mini++;
}
}
return min;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
H*1
44 楼
如果是这样，[3, 4, -1, 1]会返回5
答案应该是2
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
答案应该是2
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
m*6
45 楼
O(n)?
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
a[
【在 c****9 的大作中提到】
: 有，之前看到过，就是走一遍，遇到a[i]!=i; swap(a[a[i]] a[i]) 走一遍后第一个a[
: i]!=i的就是
: //Input Array:get first positive number that is not in the array
: int getfirstpositive(int* a, int len)
: {
: int i=0;
: while(i
: int m= a[i];
: if (m>=0&&m
G*s
46 楼
此题是 given int array in range [1,N]，find missing integer的变形吧，
in my opinion
扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
gives us O(n+k).
不知道这样做是否妥当和最有呢
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
in my opinion
扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
gives us O(n+k).
不知道这样做是否妥当和最有呢
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
g*y
48 楼
public int find(int[] a) {
int least = a.length;
for (int i=a.length-1; i>=0; i--) {
if (a[i]<=0 || a[i]>i+1) {
least = i;
continue;
}
if (a[i] != i+1) {
if (a[i] == a[a[i]-1]) {
least = i;
}
else {
int t = a[i]-1;
a[i] = a[t];
a[t] = t+1;
i++;
}
}
}
return least+1;
}
int least = a.length;
for (int i=a.length-1; i>=0; i--) {
if (a[i]<=0 || a[i]>i+1) {
least = i;
continue;
}
if (a[i] != i+1) {
if (a[i] == a[a[i]-1]) {
least = i;
}
else {
int t = a[i]-1;
a[i] = a[t];
a[t] = t+1;
i++;
}
}
}
return least+1;
}
A*u
49 楼
大牛，看不懂
可否详解
【在 g**********y 的大作中提到】
: public int find(int[] a) {
: int least = a.length;
:
: for (int i=a.length-1; i>=0; i--) {
: if (a[i]<=0 || a[i]>i+1) {
: least = i;
: continue;
: }
:
: if (a[i] != i+1) {
可否详解
【在 g**********y 的大作中提到】
: public int find(int[] a) {
: int least = a.length;
:
: for (int i=a.length-1; i>=0; i--) {
: if (a[i]<=0 || a[i]>i+1) {
: least = i;
: continue;
: }
:
: if (a[i] != i+1) {
c*2
50 楼
方法挺好的，但是好像空间不是O(1)吧
int,
【在 G**********s 的大作中提到】
: 此题是 given int array in range [1,N]，find missing integer的变形吧，
: in my opinion
: 扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
: assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
: gives us O(n+k).
: 不知道这样做是否妥当和最有呢
int,
【在 G**********s 的大作中提到】
: 此题是 given int array in range [1,N]，find missing integer的变形吧，
: in my opinion
: 扫描的时候, 用bitmap来mark seen positive ints，略过non-positive的integer，
: assume 有k个positive ints, O(n) mark positives，O(k) find first missing int,
: gives us O(n+k).
: 不知道这样做是否妥当和最有呢
g*y
51 楼
http://www.mitbbs.com/article0/JobHunting/31902917_0.html
【在 A**u 的大作中提到】
: 大牛，看不懂
: 可否详解
【在 A**u 的大作中提到】
: 大牛，看不懂
: 可否详解
s*e
52 楼
扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
。
扫描第二遍，返回第一个小于等于0的数组index。
int findPosMissing(int* arr, int size) {
for (int i=0; i
int temp = arr[i];
arr[i] = 0;
int temp1;
while (true) {
if (temp <=0 ) break;
if (temp > size ) break;
if (arr[temp-1] == temp) break;
temp1 = arr[temp-1];
arr[temp-1]= temp;
temp = temp1;
}
}
for (int i=0; i
return i+1;
}
}
return size+1;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
。
扫描第二遍，返回第一个小于等于0的数组index。
int findPosMissing(int* arr, int size) {
for (int i=0; i
int temp = arr[i];
arr[i] = 0;
int temp1;
while (true) {
if (temp <=0 ) break;
if (temp > size ) break;
if (arr[temp-1] == temp) break;
temp1 = arr[temp-1];
arr[temp-1]= temp;
temp = temp1;
}
}
for (int i=0; i
return i+1;
}
}
return size+1;
}
【在 H***e 的大作中提到】
: O(n) time, O(1) space?
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
P*A
53 楼
if (arr[i]<=0) 有问题，没考虑arr[i]>n
应该改成 if(arr[i]!=i+1)
【在 s****e 的大作中提到】
: 扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
: 。
: 扫描第二遍，返回第一个小于等于0的数组index。
: int findPosMissing(int* arr, int size) {
: for (int i=0; i
: int temp = arr[i];
: arr[i] = 0;
: int temp1;
: while (true) {
应该改成 if(arr[i]!=i+1)
【在 s****e 的大作中提到】
: 扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
: 。
: 扫描第二遍，返回第一个小于等于0的数组index。
: int findPosMissing(int* arr, int size) {
: for (int i=0; i
: int temp = arr[i];
: arr[i] = 0;
: int temp1;
: while (true) {
i*e
54 楼
他代码没问题，这里handle了：
if (temp <=0 ) break;
if (temp > size ) break;
另外随手写了一个，基于 cx3959 的思路（除了他没有handle n==0 这个状况之外，他
这个思路是挺简洁的）：
int firstMissingPositive(int A[], int n) {
if (n == 0) return 1;
for (int i = 0; i < n; i++)
while (A[i] >= 0 && A[i] < n && A[i] != A[A[i]])
swap(A[i], A[A[i]]);
for (int i = 1; i < n; i++)
if (A[i] != i) return i;
return (A[0] == n) ? n+1 : n;
}
Edit：
火鸡那个思路很巧妙，学习了！
【在 P*A 的大作中提到】
: if (arr[i]<=0) 有问题，没考虑arr[i]>n
: 应该改成 if(arr[i]!=i+1)
if (temp <=0 ) break;
if (temp > size ) break;
另外随手写了一个，基于 cx3959 的思路（除了他没有handle n==0 这个状况之外，他
这个思路是挺简洁的）：
int firstMissingPositive(int A[], int n) {
if (n == 0) return 1;
for (int i = 0; i < n; i++)
while (A[i] >= 0 && A[i] < n && A[i] != A[A[i]])
swap(A[i], A[A[i]]);
for (int i = 1; i < n; i++)
if (A[i] != i) return i;
return (A[0] == n) ? n+1 : n;
}
Edit：
火鸡那个思路很巧妙，学习了！
【在 P*A 的大作中提到】
: if (arr[i]<=0) 有问题，没考虑arr[i]>n
: 应该改成 if(arr[i]!=i+1)
h*n
55 楼
你这个怎么看出来是O(n)的复杂度呢
for里面有个while循环，求解
【在 i**********e 的大作中提到】
: 他代码没问题，这里handle了：
: if (temp <=0 ) break;
: if (temp > size ) break;
: 另外随手写了一个，基于 cx3959 的思路（除了他没有handle n==0 这个状况之外，他
: 这个思路是挺简洁的）：
: int firstMissingPositive(int A[], int n) {
: if (n == 0) return 1;
: for (int i = 0; i < n; i++)
: while (A[i] >= 0 && A[i] < n && A[i] != A[A[i]])
: swap(A[i], A[A[i]]);
for里面有个while循环，求解
【在 i**********e 的大作中提到】
: 他代码没问题，这里handle了：
: if (temp <=0 ) break;
: if (temp > size ) break;
: 另外随手写了一个，基于 cx3959 的思路（除了他没有handle n==0 这个状况之外，他
: 这个思路是挺简洁的）：
: int firstMissingPositive(int A[], int n) {
: if (n == 0) return 1;
: for (int i = 0; i < n; i++)
: while (A[i] >= 0 && A[i] < n && A[i] != A[A[i]])
: swap(A[i], A[A[i]]);
h*n
56 楼
好像大概明白了，里面while的作用是把数字放到该放的位置上
一共有n个数字，所以里面的while在整个程序里最多执行n次
不知道这么理解对不对
【在 h****n 的大作中提到】
: 你这个怎么看出来是O(n)的复杂度呢
: for里面有个while循环，求解
一共有n个数字，所以里面的while在整个程序里最多执行n次
不知道这么理解对不对
【在 h****n 的大作中提到】
: 你这个怎么看出来是O(n)的复杂度呢
: for里面有个while循环，求解
w*o
57 楼
受Rebecca9的启发写一个one pass的。把不在［1..n］之内和重复的放到尾部：
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if(A == null || A.length == 0)
return 1;
int i = 0, n = A.length - 1;
while(i <= n) {
int x = A[i];
if(x == i + 1) {
i++;
continue;
}
if(x <= 0 || x > n + 1|| x == A[x - 1]) {
A[i] = A[n--];
} else {
A[i] = A[x - 1];
A[x - 1] = x;
}
}
return i + 1;
}
public int firstMissingPositive(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if(A == null || A.length == 0)
return 1;
int i = 0, n = A.length - 1;
while(i <= n) {
int x = A[i];
if(x == i + 1) {
i++;
continue;
}
if(x <= 0 || x > n + 1|| x == A[x - 1]) {
A[i] = A[n--];
} else {
A[i] = A[x - 1];
A[x - 1] = x;
}
}
return i + 1;
}
相关阅读
中国人应该多多创业，多有自己的公司。。这样才能真正推动new国内有五年IT工作经验的人，能申请senior的工作吗？烙印的找工作论坛呢请问linkedin 的freezing period 多久valid numberOPT 加急问题facebook 对linkedin 下手了。斗胆问一下，对于小硕来说 机器学习 和前端工程师，哪个方向好一些？昨天发FLAG offer求比较的哥们删帖了有人感兴趣吗？Intel提供Google内推挖个坑：收入对应FB多久pay一次？请教 print factors 这个题youtube data scientist 面经碰到安徽土凤凰大学毕业的老中startup CEO rankingfacebook intern location选择TX的9万年薪，和MD10万年薪选哪个？find a file in linux but got permission denied as admiin