Careercup - Microsoft面试题

2014-05-12 07:44

原题：

Given an array having  unique integers, each lying within the range <x<, how do u sort it. U can load only  numbers at a time in memory.

题目：一个数组里有16000个不重复的整数，所有元素都在1和20000之间。如果你一次至多能在内存里放1000个整数，你要如何排序整个数组？

解法1：这个题目表述是不是有问题？数组本身就是内存的数据吧？内存装不下还叫数组？既然所有元素都是不重复的，就可以用位向量了。用位向量标记，就可以通过一次扫描来排序所有元素了。如果按照一个整数4字节的话，1000个整数有4000字节，总共32000个位，是足够覆盖数据范围的。如果按照16位整数来算，这个算法就不可行了。《编程珠玑》和《Cracking the Coding Interview》上都有类似的题目。内存限制是任何时候都要考虑的实际问题。如果资源总是无限的，这个世界也就没问题需要解决了。

代码：

 // http://www.careercup.com/question?id=23123665

 // all numbers are unique.

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int main()

 {

     const int MAXN = ;

     FILE *fin, *fout;

     unsigned bit[MAXN >> ];

     int i;

     memset(bit, , MAXN / );

     fin = fopen("in.txt", "r");

     while (!feof(fin)) {

         fscanf(fin, "%u", &i);

         bit[i >> ] |= ( << (i & ));

     }

     fclose(fin);

     fin = nullptr;

     fout = fopen("out.txt", "w");

     for (i = ; i < MAXN; ++i) {

         if (bit[i >> ] & ( << (i & ))) {

             fprintf(fout, "%u\n", i);

         }

     }

     fclose(fout);

     fout = nullptr;

     return ;

 }

解法2：如果元素存在重复的话，就不能用位向量了。可以用数组来分段统计每个数据范围元素出现的个数，这样能通过多次扫描达到排序的效果。

代码：

 // http://www.careercup.com/question?id=23123665

 // may contain duplicates.

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 int main()

 {

     const int MAXN = ;

     const int n = ;

     FILE *fin, *fout;

     int count[n];

     int i, j;

     int offset;

     fin = fopen("in.txt", "r");

     fout = fopen("out.txt", "w");

     if (fin == nullptr || fout == nullptr) {

         printf("File doesn't exist.\n");

         exit();

     }

     offset = ;

     while (offset < MAXN) {

         memset(count, , n * sizeof(int));

         fseek(fin, , SEEK_SET);

         while (!feof(fin)) {

             fscanf(fin, "%d", &i);

             if (i >= offset && i < offset + n) {

                 ++count[i - offset];

             }

         }

         for (i = ; i < n; ++i) {

             for (j = ; j < count[i]; ++j) {

                 fprintf(fout, "%d\n", i + offset);

             }

         }

         offset += n;

     }

     fclose(fin);

     fin = nullptr;

     fclose(fout);

     fout = nullptr;

     return ;

 }

巴特西

Careercup - Microsoft面试题 - 23123665

最新文章

热门文章