o*******y
发帖数: 115 | 1 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。
比如[1,2,0] return 3, [3,4,-1,1] return 2
版上找到的题 据说有time O(n), constant space的解
讨论一下哈 | e********r
发帖数: 2352 | 2 bool array [] = {T, T, T, T, T, T, T, T, T, …}
unsorted int array
int array2 [] = {3, 1, 2, 0, -1, …}
for(int i = 0; i < array2.size(); i++)
{
if(array2[i] > 0)
array[array2[i]] = false;
}
for(int i = 0; i < array.size(); i++)
if(array[i])
return i;
刚想的答案，看一下符合你的要求吗.
【在 o*******y 的大作中提到】
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
: 版上找到的题 据说有time O(n), constant space的解
: 讨论一下哈
| S*****e
发帖数: 229 | 3 我觉得可以用bit vector，size就是array size，扫一遍array，如果array中的整数在
bit vector之内，相应的bit变成1，之后再扫一遍bit vector，第一个0表示最小的不
在此array的数。
【在 o*******y 的大作中提到】
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
: 版上找到的题 据说有time O(n), constant space的解
: 讨论一下哈
| i***h
发帖数: 12655 | 4 数组长N, 那么答案肯定是在 1...N+1之间
假定可以改变原数组
用二分法 | i***h
发帖数: 12655 | 5 如果数组里有相同数字
我的解就不是O(N)
【在 i***h 的大作中提到】
: 数组长N, 那么答案肯定是在 1...N+1之间
: 假定可以改变原数组
: 用二分法
| o*******y
发帖数: 115 | 6 度娘的答案。。。
利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于
等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为
m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
MIN-AVAILABLE-NUM(A, low, up)
if(low == up) return low
m = (low + up) / 2
split = partition(A, low, up, m)
if a[split] == m
then return MIN-AVAILABLE-NUM(A, low, split)
else return MIN-AVAILABLE-NUM(A, split+1, up)
这里递归式为：T(n) = T(n/2) + O(n)，根据主定理的第三种情况，复杂度为O(n)，其
实也就是一个等比数列：n + n/2 + n/4...
但是，此处因为用到递归，所以空间复杂度其实是O(Lgn)，所以可以用循环来代替：
MIN-AVAILABLE-NUM(A, low, up)
while low != up
m = (low + up) / 2
split = partition(low, up, m)
if A[split] == m
then low = split + 1
else up = split - 1
return low | o*******y
发帖数: 115 | 7 但有重复元素貌似有问题啊 比如 4 4 4 4 5 6 7 8 | i***h
发帖数: 12655 | 8 你可以另外做个循环处理这种情况, 还是O(N)
【在 o*******y 的大作中提到】
: 但有重复元素貌似有问题啊 比如 4 4 4 4 5 6 7 8
| e********r
发帖数: 2352 | 9 你说的是你贴的那个答案还是指俺说的那个，俺的那个可以应对重复元素.
【在 o*******y 的大作中提到】
: 但有重复元素貌似有问题啊 比如 4 4 4 4 5 6 7 8
| i***h
发帖数: 12655 | 10 你的不是 time O(n), constant space的解
【在 e********r 的大作中提到】
: 你说的是你贴的那个答案还是指俺说的那个，俺的那个可以应对重复元素.
| | | e********r
发帖数: 2352 | 11 你是说不是constant space吗.
【在 i***h 的大作中提到】
: 你的不是 time O(n), constant space的解
| i***h
发帖数: 12655 | 12 right
【在 e********r 的大作中提到】
: 你是说不是constant space吗.
| l***i
发帖数: 1309 | 13 Use 0 to partition your array, the same idea as partition for quicksort | e********r
发帖数: 2352 | 14 请问能把partition funciton也贴出来吗，谢谢哈.
【在 o*******y 的大作中提到】
: 度娘的答案。。。
: 利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
: 取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于
: 等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为
: m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
: MIN-AVAILABLE-NUM(A, low, up)
: if(low == up) return low
: m = (low + up) / 2
: split = partition(A, low, up, m)
: if a[split] == m
| y*****n
发帖数: 243 | 15
worse case is not T(n/2)+O(n). Is T(n-1)+O(n). And use partition cannot
handle negative number.
【在 o*******y 的大作中提到】
: 度娘的答案。。。
: 利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
: 取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于
: 等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为
: m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
: MIN-AVAILABLE-NUM(A, low, up)
: if(low == up) return low
: m = (low + up) / 2
: split = partition(A, low, up, m)
: if a[split] == m
| y*****n
发帖数: 243 | 16 结果必然在0到n+1之中。我们可以这样，扫描一遍数组，如果a[i]上的数为m，就找到a
[m]看里面的数是什么。如果是a[m]不是m我们就把a[i]a[m]换个位置。如果a[i]<0 or
>n就不要找a[m]了。这样一来最后大小为m的必然在a[m]位置上，如果a[m]位置上不为m
，那么这个m就是我们要找的值了。空间0时间O(n)
public static int getFirstPositive(int[] a) {
int i = 0;
while (i < a.length) {
int m = a[i];
if (m>=0 && m
int tmp = a[m];
a[m] = a[i];
a[i] = tmp;
}else i++;
}
for(i = 1;i< a.length;i++){
if(a[i] != i) return i;
}
return a.length;
}
public static void main(String [] args){
int[] t1 = {1,2,0};
int[] t2 = {3,4,-1,1};
System.out.println(getFirstPositive(t1));
System.out.println(getFirstPositive(t2));
} | S*****e
发帖数: 229 | 17 好方法。我之前说的那个没注意到const space。
到a
or
为m
【在 y*****n 的大作中提到】
: 结果必然在0到n+1之中。我们可以这样，扫描一遍数组，如果a[i]上的数为m，就找到a
: [m]看里面的数是什么。如果是a[m]不是m我们就把a[i]a[m]换个位置。如果a[i]<0 or
: >n就不要找a[m]了。这样一来最后大小为m的必然在a[m]位置上，如果a[m]位置上不为m
: ，那么这个m就是我们要找的值了。空间0时间O(n)
: public static int getFirstPositive(int[] a) {
: int i = 0;
: while (i < a.length) {
: int m = a[i];
: if (m>=0 && m: int tmp = a[m];
| w****o
发帖数: 2260 | 18 你的方法很好。
不过我发现了一个小的bug,
就是最后的处理，如果a[1],..., a[n-1]都有相应的值1, ..., n-1, 这时应该在检查
一下a[0],如果a[0]是n,的话，应该返回n+1,可是你的程序返回n,
比如{3, 1, 2},最后的救过应该是4， 而不应该是3.
到a
or
为m
【在 y*****n 的大作中提到】
: 结果必然在0到n+1之中。我们可以这样，扫描一遍数组，如果a[i]上的数为m，就找到a
: [m]看里面的数是什么。如果是a[m]不是m我们就把a[i]a[m]换个位置。如果a[i]<0 or
: >n就不要找a[m]了。这样一来最后大小为m的必然在a[m]位置上，如果a[m]位置上不为m
: ，那么这个m就是我们要找的值了。空间0时间O(n)
: public static int getFirstPositive(int[] a) {
: int i = 0;
: while (i < a.length) {
: int m = a[i];
: if (m>=0 && m: int tmp = a[m];
| q****x
发帖数: 7404 | 19 走火入魔。
【在 o*******y 的大作中提到】
: 题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。
: 比如[1,2,0] return 3, [3,4,-1,1] return 2
: 版上找到的题 据说有time O(n), constant space的解
: 讨论一下哈
| S**Y
发帖数: 136 | 20 啥意思？
【在 q****x 的大作中提到】
: 走火入魔。
| | | c*z
发帖数: 86 | 21 思路同 yezhuen。
#include
#define V(i) (i + 1) /* Expected value of index i */
#define I(x) (x - 1) /* Expected index of value x */
int go(int *x, int n)
{
int i, t;
for (i = 0; i < n; i ++) {
while (x[i] > 0 && x[i] <= n &&
x[i] != V(i) &&
x[I(x[i])] != x[i]) {
t = I(x[i]);
x[i] = x[t];
x[t] = V(t);
}
}
for (i = 1; i < n; i ++) {
if (x[i] != V(i)) {
return V(i);
}
}
return V(n);
}
int main()
{
int x[4] = {3, 4, -1, 1};
printf("%d\n", go(x, 4));
return 0;
} | b***u
发帖数: 12010 | 22 array的size是2 billion。你打算说服考官这是O(1)么？
【在 e********r 的大作中提到】
: 请问能把partition funciton也贴出来吗，谢谢哈.
| P*******y
发帖数: 168 | 23 这个对于有重复的数就不能处理了
比如4 2 3 4
返回的会是4
到a
or
为m
【在 y*****n 的大作中提到】
: 结果必然在0到n+1之中。我们可以这样，扫描一遍数组，如果a[i]上的数为m，就找到a
: [m]看里面的数是什么。如果是a[m]不是m我们就把a[i]a[m]换个位置。如果a[i]<0 or
: >n就不要找a[m]了。这样一来最后大小为m的必然在a[m]位置上，如果a[m]位置上不为m
: ，那么这个m就是我们要找的值了。空间0时间O(n)
: public static int getFirstPositive(int[] a) {
: int i = 0;
: while (i < a.length) {
: int m = a[i];
: if (m>=0 && m: int tmp = a[m];
| P*******y
发帖数: 168 | 24 刚想错了，返回应该是1
这算法对的
【在 P*******y 的大作中提到】
: 这个对于有重复的数就不能处理了
: 比如4 2 3 4
: 返回的会是4
:
: 到a
: or
: 为m
|
|
