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

问题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)。

void RightShift(char *str, int k)
{
    if(str == NULL)
    {
        return;
    }
    int length = strlen(str);
    k = k % length;

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


    while(tmp--)
    {
        char temp = str[length - 1];
        for(i = length - 1; i > 0; i--)
        {
            str[i] = str[i - 1];
        }
        str[0] = temp;
    }
}

    方法二：
    三次翻转，时间复杂度为O(n)。

//三次逆转
void Swap(char *a, char *b)
{
    char temp = *a;
    *a = *b;
    *b = temp;
}

void Reverse(char *str, int left, int right)
{
    if(str == NULL || left >= right)
    {
        return;
    }
    while(left < right)
    {
        Swap(&str[left], &str[right]);
        left++;
        right--;
    }
}

void RightShift(char *str, int k)
{
    if(str == NULL)
    {
        return;
    }
    int length = strlen(str);
    k = k % length;

    Reverse(str, 0, k - 1);
    Reverse(str, k , length - 1);
    Reverse(str, 0 , length - 1);
}

    方法三：
    定义两个指针，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++

//
void Swap(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}
void RightShift(char *str, int m)
{
    if(str == NULL)
    {
        return;
    }

    int length = strlen(str);
    m = m % length;
    if(m <= 0)
    {
        return;
    }

    int p1 = 0;
    int p2 = m;
    int k = (length - m) - length % m;

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

    //处理尾部，r为尾部左移动的字符个数,
    //前后交换的方法
    int r = length - p2;
    while(r--)
    {
        int i = p2;
        while(i > p1)
        {
            Swap(&str[i], &str[i - 1]);
            i--;
        }
        p1++;
        p2++;
    }
}

    方法四
    对于左旋转字符串，我们知道每个单元都需要且只需要赋值一次，什么样的序列能保证每个单元都只赋值一次呢？
    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)个循环链，对每个循环链分布进行一次内循环就可以了。

int gcd(int n, int m)
{
    if(n < m)
    {
        int tmp = n;
        n = m;
        n = tmp;
    }
    int r = 1;
    while(r)
    {
        r = n % m;
        n = m;
        m = r;
    }
    return n;
}

void RightShift(char *str, int m)
{
    if(str == NULL)
    {
        return;
    }

    int length = strlen(str);
    m = m % length;
    int numofgroup = gcd(length, m);    //循环链个数

    int eleminsub = length / numofgroup;//每个循环链上的个数

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

        for(j = 0; j < eleminsub - 1; j++)//注意
        {
            //内循环次数i为：每个循环链上的元素个数，n/gcd(length, m)次
            str[(i + j * m) % length] = str[(i + (j + 1) * m) % length];
        }
        str[(i + j * m) % length] = tmp;
    }
}

    方法五
    素数法



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