c***7
发帖数: 315 | 1 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
， time O(n), space O(n)。 求time O(n), constant space的解。。。
2.Given P machines, each containing an array of N elements, find the medium
of the array resulted by concatenating all the arrays on the machines. You
cannot move data across machines. |
c****p
发帖数: 6474 | 2 第1题 前面版上讨论过了
先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
再扫第二遍，对于每个Ai，
如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
如果Ai<1 或者Ai>max直接忽略。
最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
integers
medium
【在 c***7 的大作中提到】
: 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
: 2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
: ， time O(n), space O(n)。 求time O(n), constant space的解。。。
:
: 2.Given P machines, each containing an array of N elements, find the medium
: of the array resulted by concatenating all the arrays on the machines. You
: cannot move data across machines.
|
c****p
发帖数: 6474 | 3 大体思路如此，可能有问题没有考虑到。
1
【在 c****p 的大作中提到】
: 第1题 前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium
|
D********g
发帖数: 650 | 4 第二题
１．每台机器sort array, NlgN
2. Maintain一个size为P的min-heap，heap的每个元素是1中每个array当前最小元素
的值和array的id (1 -- p )，以及指向对应array首部的pointer，heap里的元素是按
照array当前最小元素排列的。
3. 对heap的根，increment 对应array的pointer.然后update heap。重复直道找到Ｎ*
P/2个元素为止。
integers
medium
【在 c***7 的大作中提到】
: 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
: 2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
: ， time O(n), space O(n)。 求time O(n), constant space的解。。。
:
: 2.Given P machines, each containing an array of N elements, find the medium
: of the array resulted by concatenating all the arrays on the machines. You
: cannot move data across machines.
|
a****a
发帖数: 186 | 5 感觉第二题思路跟external sort思路大同小异。
integers
medium
【在 c***7 的大作中提到】
: 1.题目是给定一个unsorted int array, 怎么找到第一个大于0，并且不在此array的
: integer。比如[1,2,0] return 3, [3,4,-1,1] return 2
: 2个算法，一个是sorting: time O(nlogn), space O(1), 一个是bitmap of integers
: ， time O(n), space O(n)。 求time O(n), constant space的解。。。
:
: 2.Given P machines, each containing an array of N elements, find the medium
: of the array resulted by concatenating all the arrays on the machines. You
: cannot move data across machines.
|
a****a
发帖数: 186 | 6 这个方法也不一定省space？
temp array长度大概也跟O(n)差不多了，如果基本都是正数
1
【在 c****p 的大作中提到】
: 第1题 前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium
|
s******n
发帖数: 3946 | 7 不用记min, negative之类的东西。直接扫描把1放到位置1(A[0])，2放到位置2，<=0不
处理。
for (int i=0; i
while (A[i]>0 && A[i]！=i+1 && A[i]<=A.length) {
int tmp = A[A[i]-1] ;
A[A[i]-1] = A[i];
A[i] = tmp;
}
}
for (int i=0; i
if (A[i]!=i+1) {
printf("%d\n", i+1);
break;
}
}
1
【在 c****p 的大作中提到】
: 第1题 前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium
|
s******n
发帖数: 3946 | 8 第二题，就是搞2个Heap来实现。
Heap1：MaxHeap, Heap2：MinHeap，保持Heap1.size==Heap2.size或者Heap1.size==
Heap2.size+1
void addNum(int num) {
if (Heap1.size==Heap2.size+1) {
if (num<=Heap1.maxValue()) {
int heap1MaxValue = Heap1.pop();
Heap2.add(heap1MaxValue);
Heap1.add(num);
} else Heap2.add(num);
} else {
if (num>=Heap2.MinValue()) {
int heap2MinValue = Heap2.pop();
Heap1.add(heap2MinValue);
Heap2.add(num);
} else Heap1.add(num);
}
}
多个机器的问题：从每个机器读一个block过来，效率比较好 |
c****p
发帖数: 6474 | 9 inplace
【在 a****a 的大作中提到】
: 这个方法也不一定省space？
: temp array长度大概也跟O(n)差不多了，如果基本都是正数
:
: 1
|
c****p
发帖数: 6474 | 10 min算是小优化。。n_positve起到相当于a.length、防止越界的作用。
更深的小优化还有：先令max = n_positive，每发现一个大于max的数，都忽略之并令m
ax--，
只是这样做可能会漏数，所以就没在原帖里写。【 在 swanswan (swan) 的大作中提到 |
|
|
a***g
发帖数: 234 | 11 为什么需要第一遍？
1
【在 c****p 的大作中提到】
: 第1题 前面版上讨论过了
: 先扫一遍，记下n_positive和min，并令max = n_pos；如果min>1 return 1;
: 再扫第二遍，对于每个Ai，
: 如果1<=Ai<=max，将A[i]和A[A[i]-1]交换；
: 如果Ai<1 或者Ai>max直接忽略。
: 最后扫一遍，i=0...max-1，如果有A[i] != i + 1 则return i+1，否则return max+1
:
: integers
: medium
|
s******n
发帖数: 3946 | 12 一次扫描就够了，小于等于0或者大于a.length的数字直接无视，[1,a.length]之间的
数字搬位置就行了。然后从头找第一个A[i]!=i+1
令m
【在 c****p 的大作中提到】
: min算是小优化。。n_positve起到相当于a.length、防止越界的作用。
: 更深的小优化还有：先令max = n_positive，每发现一个大于max的数，都忽略之并令m
: ax--，
: 只是这样做可能会漏数，所以就没在原帖里写。【 在 swanswan (swan) 的大作中提到
|
p********n
发帖数: 20 | 13 这个还要考虑A数组中可能含相同的数吧
【在 s******n 的大作中提到】
: 不用记min, negative之类的东西。直接扫描把1放到位置1(A[0])，2放到位置2，<=0不
: 处理。
: for (int i=0; i: while (A[i]>0 && A[i]！=i+1 && A[i]<=A.length) {
: int tmp = A[A[i]-1] ;
: A[A[i]-1] = A[i];
: A[i] = tmp;
: }
: }
: for (int i=0; i
|
s******o
发帖数: 2233 | 14 try A = {1, 1}
it will end up with an infinite loop
You need to change the condition to:
while (A[i]>0 && A[A[i]-1]!=A[i] && A[i]<=A.length)
【在 s******n 的大作中提到】
: 不用记min, negative之类的东西。直接扫描把1放到位置1(A[0])，2放到位置2，<=0不
: 处理。
: for (int i=0; i: while (A[i]>0 && A[i]！=i+1 && A[i]<=A.length) {
: int tmp = A[A[i]-1] ;
: A[A[i]-1] = A[i];
: A[i] = tmp;
: }
: }
: for (int i=0; i
|
s*****r
发帖数: 773 | 15 这个时间复杂度是多少？ O（n） ？
但是每个while循环可能执行很多次啊
【在 s******o 的大作中提到】
: try A = {1, 1}
: it will end up with an infinite loop
: You need to change the condition to:
: while (A[i]>0 && A[A[i]-1]!=A[i] && A[i]<=A.length)
|
