算法题一：Given 1 GB memory, input a file which contians 4 billion integers,
output one integer that is not in the file. What if you have only 10 MB
memory?
算法题二：There are 100 hundred sorted arrays, and each of them contains 100
numbers. Give an algorithm to merge them into a single sorted array, using
only one temporary array in the middle steps.
编程题：Input an integer array of size n and an integer k (k<=n), output all
subsets of size k.
szuxjq
Member
算法题一有没有点提示？
算法题二 似乎是升级版merge sort的一部分
qqpeter
Member
算法二思路
1. 取100个数组中各自的第一个数，组成一个最小堆。
2. 输出堆中的最小值，并且把这个最小值对应的数组的第二个数加入堆，并且调整。
3. 重复步骤2直到所有数组中的值都被输出。
空间需要为一个长度为100的临时数组。
Wanting
Member
第一题可以用bit array来做
如果只有10mb的话可以用multi pass来做
Wanting
Member
第三题
void outputSubArrayHelper(int input[], int n, int k, int startIndex, int result[], int resultIndex);
void outputSubArray(int input[], int n, int k) {
if ((input == NULL) || (n <= 0) || (k <= 0) || (k > n)) return;
int* result = new int[k];
outputSubArrayHelper(input, n, k, 0, result, 0);
delete result;
}
void outputSubArrayHelper(int input[], int n, int k, int startIndex, int result[], int resultIndex) {
if (resultIndex == k) {
for (int i = 0; i < k; i++) {
printf("%i ", result[i]);
}
printf("\n");
return;
}
if ((n - startIndex) < (k - resultIndex)) return; //There is no sufficient elements left to form the subarray.
for (int i = startIndex; i < n; i++) {
result[resultIndex] = input[i];
outputSubArrayHelper(input, n, k, i + 1, result, resultIndex + 1);
}
}
Sainkei
Member
算法题1或许可以这样解决：
建立一个1G的内存的数组intArr，这个数组可以存256M个整数，初始时intArr[i] = i (0<=i<256M)
现在从文件读入一个数字x，如果有intArr[x%256M] == x，则
1、如果intArr[x%256M]<4G 则intArr[x%256M] += 256M，否则
2、intArr[x%256M] = (某种特殊标志NaN)。
按上述方法读完文件中的所有4G数字。
最后在intArr中找出不时特殊标志NaN的数字即可。
10M内存时算法类似。
Sainkei
Member
sorry,上面所说是错的。汗！
应该用bit建立一个二叉树来解
第一题
如果不考虑整型表示范围（题目似乎也没强调），那么有个很简单的方法：
遍历一遍，找到最小值min， 输出 min-1 就哦了。
如果有范围，比如sizeof(int)=4，Wanting 的bit标记法应该可以很容易解1GB. 而对于10MB的情况，bit标记法最坏情况下要pass 50遍。 用 取模MOD 做可能会快一些
Yuanyuan
Member
。。。。。。。。。。。
你必须 登录 后发帖。
