编程珠玑——第二章问题AB

2190阅读　0评论2013-06-08　梦醒潇湘love
分类：C/C++


问题A：
    给定最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的数——为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，达十年后仅有几百字节的内存，又该如何解决？
解答：
    （1）如果具有足够的内存，可用采用位图法进行解决。需要2^32/8/1024/1024 = 512MB的内存。如果某个数在在文件中，那么将其在BitMap中的位置设置为1，如果不存在于文件中，则设为0；遍历文件中，进行遍历BitMap，遇到某一位为0，则说明这个数不在文件中。
    （2）如果对内存有严格的限制，位图法就不可取了（其实也可以的）。这里利用二分的思想：因为二进制中的每一位要么是0要么是1，因此可以根据数据的某一位来分，该位为1的分配在一组，该位为0的分配在另一组。
    对于40亿数字来说，进行如下的操作：从最高位到最低位，当然，从最低位到最高位也可以。按照上面的思想进行分组，例如对于最高位为1的分在一组，最高位为0的分在另一组，这样40亿数据就被分成了两组，下面观察这两组数据。
    经过上面的划分后两组数据可能有下面的情况：
    情况一：因为两组数有相同的个数，那么可以判断这两组数中都缺失了2^32个中的某一个或者多个；
    情况二：可以肯定的是小的那部分数据缺少某一个或者多个数，而多的那一部分是不确定的，当然可以判断出来（通过与2^32/2 = 2^31比较）；
    对于情况一来说，可以任选一组数继续进行二分操作；对于情况二来说，选择数据量小的那部分数据继续进行二分操作，这样不断的进行下去，就可以找到某个不在40亿数中的数了。
    这里很巧妙的利用了二分法，而且与平常使用的二分查找不太相同。这里是根据一个数的某一位来将数据分配到不同的组中。

    上面的就是这个问题的大概思路：用位图法很直接，但会占用比较大的内存；利用二分法比较巧妙，不太容易想到。


问题B：
    将一个n元一维向量向左旋转i个位置。例如，当n = 8且i = 3时，向量abcdefgh旋转为defghabc。
解法：
    方法一
    采用每次向右移动一位的方法，循环length - k次。该方法比较笨，但是也是最容易想到的，时间复杂度为O(n^2)。
  1. void RightShift(char *str, int k)
  2. {
  3.     if(str == NULL)
  4.     {
  5.         return;
  6.     }
  7.     int length = strlen(str);
  8.     k = k % length;

  10.     int i = 0;
  11.     int tmp = length - k;//注意这里呢

  13.     
  14.     while(tmp--)
  15.     {
  16.         char temp = str[length - 1];
  17.         for(i = length - 1; i > 0; i--)
  18.         {
  19.             str[i] = str[i - 1];
  20.         }
  21.         str[0] = temp;
  22.     }
  23. }
    方法二：
    三次翻转，时间复杂度为O(n)。
  1. //三次逆转
  2. void Swap(char *a, char *b)
  3. {
  4.     char temp = *a;
  5.     *a = *b;
  6.     *b = temp;
  7. }

  9. void Reverse(char *str, int left, int right)
  10. {
  11.     if(str == NULL || left >= right)
  12.     {
  13.         return;
  14.     }
  15.     while(left < right)
  16.     {
  17.         Swap(&str[left], &str[right]);
  18.         left++;
  19.         right--;
  20.     }
  21. }

  23. void RightShift(char *str, int k)
  24. {
  25.     if(str == NULL)
  26.     {
  27.         return;
  28.     }
  29.     int length = strlen(str);
  30.     k = k % length;

  32.     Reverse(str, 0, k - 1);
  33.     Reverse(str, k , length - 1);
  34.     Reverse(str, 0 , length - 1);
  35. }
    方法三：
    定义两个指针，p1指向str[0]，p2指向str[m]；
    以下过程循环m次，交换p1和p2所指向的元素，然后p1++,p2++；
    第一步，交换abc和def
    abc defghi -> def abcghi
    第二步，交换abc和ghi
    def abcghi -> def ghiabc
    整个过程看起来就是abc一步一步向后移动，时间复杂度为O(n+m)。
    总结一下该思路：
    A. 首先让p1 = str[0]，p2 = str[m]，即让p1和p2相隔m的距离；
    B. 判断p2＋ｍ－１是否越界，如果没有越界转到C，否则转到D（abcdefgh这8个字符的字符串，以4左旋，那么初始化时p2指向e，p2+4越界了，但事实上p2至p2+m-1是m个字符，可以再做一次交换）；
    C. 不断交换*p1和*p2，然后p1++,p2++，循环m次，然后转到2；
    D. 此时p2+m-1已经越界，在此只需要处理尾巴。过程如下所示：
            通过n-p2得到p2与尾部之间元素个数r，即我们要前移的元素个数；
            以下过程执行r次：
                ch[p2] <-> ch[p2-1]，ch[p2-1]<->ch[p2-2]，.......，ch[p1+1] <->ch[p1];p1++,p2++
  1. //
  2. void Swap(char *a, char *b)
  3. {
  4.     char tmp = *a;
  5.     *a = *b;
  6.     *b = tmp;
  7. }
  8. void RightShift(char *str, int m)
  9. {
  10.     if(str == NULL)
  11.     {
  12.         return;
  13.     }

  15.     int length = strlen(str);
  16.     m = m % length;
  17.     if(m <= 0)
  18.     {
  19.         return;
  20.     }

  22.     int p1 = 0;
  23.     int p2 = m;
  24.     int k = (length - m) - length % m;

  26.     //交换p1和p2指向的元素，然后移动p1、p2
  27.     while(k--)
  28.     {
  29.         Swap(&str[p1], &str[p2]);
  30.         p1++;
  31.         p2++;
  32.     }

  34.     //处理尾部，r为尾部左移动的字符个数,
  35.     //前后交换的方法
  36.     int r = length - p2;
  37.     while(r--)
  38.     {
  39.         int i = p2;
  40.         while(i > p1)
  41.         {
  42.             Swap(&str[i], &str[i - 1]);
  43.             i--;
  44.         }
  45.         p1++;
  46.         p2++;
  47.     }
  48. }
    方法四
    对于左旋转字符串，我们知道每个单元都需要且只需要赋值一次，什么样的序列能保证每个单元都只赋值一次呢？
    A. 对于正整数m、n互为质数的情况，通过以下过程得到序列的满足上面的要求：
    for i = 0:n-1
        k = i * m % n;
    end
    举个例子来说明下，例如对于m = 3, n =4的情况：
        我们得到的序列：即通过上述式子求出来的k序列，是0, 3, 2, 1
        然后，你只要只需按这个顺序赋值一遍就达到了左旋3的目的了：
        ch[0] - > tmp, ch[3] -> ch[0], ch[2] -> ch[3], ch[1]-> ch[2], tmp - > ch[1]   
    这个赋值的式子就是依次赋值的序列，这个确实很巧妙，以上只是特例，作为一个循环链，相当于rotate算法的一次内循环。
    
    B. 对于正整数m、n不是互为质数的情况（因为不可能所有的m、n都是互质整数对），那么我们把它分成一个个互不影响的循环链，所有序号为(j + i * m)%n（j为0到gcd(n,m) - 1）之间的某一个整数，i = 0：n-1）会构成一个循环链，一共有gcd(n,m)个循环链，对每个循环链分布进行一次内循环就可以了。
  1. int gcd(int n, int m)
  2. {
  3.     if(n < m)
  4.     {
  5.         int tmp = n;
  6.         n = m;
  7.         n = tmp;
  8.     }
  9.     int r = 1;
  10.     while(r)
  11.     {
  12.         r = n % m;
  13.         n = m;
  14.         m = r;
  15.     }
  16.     return n;
  17. }

  19. void RightShift(char *str, int m)
  20. {
  21.     if(str == NULL)
  22.     {
  23.         return;
  24.     }

  26.     int length = strlen(str);
  27.     m = m % length;
  28.     int numofgroup = gcd(length, m);    //循环链个数
  29.     
  30.     int eleminsub = length / numofgroup;//每个循环链上的个数

  32.     int i, j;
  33.     for(i = 0; i < numofgroup; i++)
  34.     {    
  35.         //外循环次数i为循环链的个数，即gcd(length,m)个循环链
  36.         char tmp = str[i];

  38.         for(j = 0; j < eleminsub - 1; j++)//注意
  39.         {
  40.             //内循环次数i为：每个循环链上的元素个数，n/gcd(length, m)次
  41.             str[(i + j * m) % length] = str[(i + (j + 1) * m) % length];
  42.         }
  43.         str[(i + j * m) % length] = tmp;
  44.     }
  45. }
    方法五
    素数法



    参考：
    左移动字符串的某些思路来自：http://blog.csdn.net/v_JULY_v


    

    
上一篇：编程珠玑——第一章习题解答
下一篇：字符串相关问题（一）