H***e
发帖数: 476 | 1 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
发帖数: 164 | 2 有，之前看到过，就是走一遍，遇到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;
} |
s******n
发帖数: 3946 | 3 [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
|
c****9
发帖数: 164 | 4 我试了下没有越界，因为会跳过负数
【在 s******n 的大作中提到】
: [3,4,-1,1] 下标越界
:
: a[
|
s******n
发帖数: 3946 | 5 跳过就好了
【在 c****9 的大作中提到】
: 我试了下没有越界，因为会跳过负数
|
w****o
发帖数: 2260 | 6 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
]==n
【在 s******n 的大作中提到】
: 跳过就好了
|
e***l
发帖数: 710 | |
w****o
发帖数: 2260 | 8 这个不会的。
a[0]=2, a[2]=2, 所以他们不会swap
【在 e***l 的大作中提到】
: [2,1,2] 死循环？
|
s*****r
发帖数: 773 | 9 那如果这样呢 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
|
c***g
发帖数: 472 | 10 用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
|
|
|
c****9
发帖数: 164 | 11 嗯，对的。确实有这个bug，已改
[0
【在 w****o 的大作中提到】
: 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
: ]==n
|
c****9
发帖数: 164 | 12 不会越界，因为跳过了，不需要额外是space， 是通过判断index的得到结论的，因为n
个元素那个最小的正数肯定在0到n+1的范围。
【在 s*****r 的大作中提到】
: 那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
:
: a[
|
R******9
发帖数: 267 | 13 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 = min
i++;
}
}
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
|
n*s
发帖数: 752 | 14 what if a={100}
【在 R******9 的大作中提到】
: 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 = min
|
H*****1
发帖数: 4815 | 15 如果是这样，[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
|
m******6
发帖数: 82 | 16 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
|
G**********s
发帖数: 70 | 17 此题是 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
|
g**********y
发帖数: 14569 | 18 这个有问题，过不了test case:
{5, 5, 5, 5, 5}
{1,2,0}
{3,4,-1,1}
【在 R******9 的大作中提到】
: 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 = min
|
g**********y
发帖数: 14569 | 19 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;
} |
A**u
发帖数: 2458 | 20 大牛，看不懂
可否详解
【在 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
发帖数: 173 | 21 方法挺好的，但是好像空间不是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).
: 不知道这样做是否妥当和最有呢
|
g**********y
发帖数: 14569 | |
s****e
发帖数: 638 | 23 扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
。
扫描第二遍，返回第一个小于等于0的数组index。
int findPosMissing(int* arr, int size) {
for (int i=0; i
if (arr[i] == i+1) continue;
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
if (arr[i]<=0){
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
发帖数: 189 | 24 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: if (arr[i] == i+1) continue;
: int temp = arr[i];
: arr[i] = 0;
: int temp1;
: while (true) {
|
i**********e
发帖数: 1145 | 25 他代码没问题，这里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)
|
H***e
发帖数: 476 | 26 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
发帖数: 164 | 27 有，之前看到过，就是走一遍，遇到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;
} |
s******n
发帖数: 3946 | 28 [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
|
c****9
发帖数: 164 | 29 我试了下没有越界，因为会跳过负数
【在 s******n 的大作中提到】
: [3,4,-1,1] 下标越界
:
: a[
|
s******n
发帖数: 3946 | 30 跳过就好了
【在 c****9 的大作中提到】
: 我试了下没有越界，因为会跳过负数
|
|
|
w****o
发帖数: 2260 | 31 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
]==n
【在 s******n 的大作中提到】
: 跳过就好了
|
e***l
发帖数: 710 | |
w****o
发帖数: 2260 | 33 这个不会的。
a[0]=2, a[2]=2, 所以他们不会swap
【在 e***l 的大作中提到】
: [2,1,2] 死循环？
|
s*****r
发帖数: 773 | 34 那如果这样呢 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
|
c***g
发帖数: 472 | 35 用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
|
c****9
发帖数: 164 | 36 嗯，对的。确实有这个bug，已改
[0
【在 w****o 的大作中提到】
: 如果[ 4 1 2 3 ], 上面的代码返回是4，正确应是5, 所以还应有一个判断，是不是a[0
: ]==n
|
c****9
发帖数: 164 | 37 不会越界，因为跳过了，不需要额外是space， 是通过判断index的得到结论的，因为n
个元素那个最小的正数肯定在0到n+1的范围。
【在 s*****r 的大作中提到】
: 那如果这样呢 1， 100， 1000，会越界么？ 那要多少space?
:
: a[
|
R******9
发帖数: 267 | 38 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 = min
i++;
}
}
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
|
n*s
发帖数: 752 | 39 what if a={100}
【在 R******9 的大作中提到】
: 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 = min
|
H*****1
发帖数: 4815 | 40 如果是这样，[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
|
|
|
m******6
发帖数: 82 | 41 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
|
G**********s
发帖数: 70 | 42 此题是 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
|
g**********y
发帖数: 14569 | 43 这个有问题，过不了test case:
{5, 5, 5, 5, 5}
{1,2,0}
{3,4,-1,1}
【在 R******9 的大作中提到】
: 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 = min
|
g**********y
发帖数: 14569 | 44 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;
} |
A**u
发帖数: 2458 | 45 大牛，看不懂
可否详解
【在 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
发帖数: 173 | 46 方法挺好的，但是好像空间不是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).
: 不知道这样做是否妥当和最有呢
|
g**********y
发帖数: 14569 | |
s****e
发帖数: 638 | 48 扫描一遍数组，<=0的数字不管，大于数组长度的数字扔掉，其余的重新排列在数组中
。
扫描第二遍，返回第一个小于等于0的数组index。
int findPosMissing(int* arr, int size) {
for (int i=0; i
if (arr[i] == i+1) continue;
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
if (arr[i]<=0){
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
发帖数: 189 | 49 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: if (arr[i] == i+1) continue;
: int temp = arr[i];
: arr[i] = 0;
: int temp1;
: while (true) {
|
i**********e
发帖数: 1145 | 50 他代码没问题，这里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)
|
|
|
h****n
发帖数: 1093 | 51 你这个怎么看出来是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]]);
|
h****n
发帖数: 1093 | 52 好像大概明白了，里面while的作用是把数字放到该放的位置上
一共有n个数字，所以里面的while在整个程序里最多执行n次
不知道这么理解对不对
【在 h****n 的大作中提到】
: 你这个怎么看出来是O(n)的复杂度呢
: for里面有个while循环，求解
|
w***o
发帖数: 109 | 53 受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;
} |
