1.二进制数中1的个数

①有一个字节（8bit）变量，求其二进制表示中"1"的个数。

思路一：二进制数的最低位如果为1，那么它不可以被2整除，反之可以。我们可以先判断最后一位是否为1，然后右移一位，重复判断最后一位是否为1，直至该数为0；这个算法时间复杂度为O(N)，其中N是这个二进制数的位数；

思路二：对于一个二进制数X，运算X&(X-1)可以将最后二进制表示中的最后一位1置为0，重复该操作直至该数为0；这个算法时间复杂度为O(M)，其中M为二进制表示中1的个数；

代码：

 

int Count(int v){    int num = 0;    while(v)[        num += v & 0x01;        v >> 1;    ]    return num;}int Count(int v){    int num = 0;    while(v){        num++;        v = v & (v-1);    }    return num;}

②给定两个整数（二进制形式表示）A和B，问把A变为B需要改变多少位(bit)？

举例说明，为了减少复杂度，就使用八位二进制吧。设 A = 0010 1011， B = 0110 0101.

1. C = A & B = 0010 0001；

2. D = A | B = 0110 1111；

3. E = C ^ D = 0100 1110；

4. 结果E中有4个1，那么也就是说将A变成B，需要改变4位（bit）。

至于如何判断E的二进制表示中有几个1，可以采用快速移位与方法。

算法原理如下：

1. A & B，得到的结果C中的1的位表明了A和B中相同的位都是1的位，C中为1的位在D中必然也为1；

2. A | B， 得到的结果D中的1的位表明了A和B在该位至少有一个为1的位，包含了A 与 B 都是1的位数，D中为0的位在C中必然也为0；

经过前两步的位运算，C 中1的位表明了A 和 B在该位都是1，D中为0的位表明了A 和 B 在该位都是0 ，所以进行第三步。

3. C ^ D，E 中为1的位表明了A 和 B不同的位。

2.阶乘相关

 

①给定一个整数N，那么N! 末尾有多少个0呢？例如N=10，N!=3628800，N!末尾有2个0。

思路：如果N! = K * 10^M，其中K不能被10整除，那么N! 的末尾就有M个0，考虑对N! 进行质因数分解，N! = (2 ^ X) * (3 ^ Y) * (25 ^ Z)....，由于2 * 5 =10；所以M和X、Z一定相关，一对2和5相乘可以得到一个10，于是M=MIN(X,Z)，不难看出X必然大于Z，所以M = Z；也就是要计算i(i = 0,1,2...N)的因式分解中5的指数，然后求和。

方法一：依次求每个数能贡献几个5

 

int ret = 0;for(int i = 1; i < N; i++){    int j = i;    while(j){        if(j%5 == 0)            ret++;        j/=5;    }}

方法二：

 

1到N的N个数中，可以被5整除的有N/5个，它们均贡献1个5；可以被25整除的有N/25个，它们在刚才的过程中贡献了一个5，然后又贡献第二个5；同理，能被125整除的贡献第三个5，依此类推...

 

int ret = 0;while(N){    ret += N/5;    N/=5;    }

②求N!的二进制表示中最低位1的位置

 

思路一：忽略掉除最低位1的其它所有1，如果这个1在第M位，那么我们发现这个数等于2 ^ (M-1)，也就是说我们可以看原来的数中有多少个质因子2，这个数就是M-1。

 

int lastOne{    int ret = 0;    while(N){        N >> 1;        ret += N;     }    return N + 1;}

思路二：N!中含有的质因数2的个数，还等于N减去N的二进制表示中1的数目。

 

例如，假设N=11011，那么N!中含有质因数2的个数为N/2+N/4+N/8+...即，

1101 + 110 + 11 + 1 = {1000 + 100 + 1} + {100 + 10} + {10 + 1} + 1 = {1000 + 100 + 10 + 1} + {100 + 10 + 1} + 1 = 1111 + 111 + 1

={10000 - 1} + {1000 - 1} + {10 - 1} + {1 - 1}  = 11011-N中1的个数。

③给定整数n，判断它是否是2的方幂。

其实就是判断二进制表示中是否只有一个1，n > 0 && ((n & (n-1)) == 0)

3.寻找发帖水王

①论坛中某个人发帖数量超过总帖子的一半，如果有一个当前论坛上所有帖子的列表，帖子作者的ID也在其中，如何找到这个发帖数超过一半的人的ID？

思路一：将这些ID排序，如果有N个帖子，那么处于第N/2处的帖子的作者就是该水王，时间复杂度为O(N*logN)。

思路二：从这些帖子中找出发帖者不同的两个ID，删除这两个帖子，在剩下的帖子中，水王发过的帖子仍然占一半以上，重复此操作，那么剩下的一定是水王的ID；

 

Type findMaxId(Type * arr,int N){    Type candidate;    int nTimes,i;    for(i = 0; i < N; i++){        //两种情况下nTimes=0，即对于i=0和成对删除直至nTime=0        if(nTimes = 0){            candidate = arr[i];            nTimes = 1;        }        else{            if(candidate == arr[i])                nTimes++;            else                nTimes--;        }    }    return candidate;}

②有三个发帖很多的水王，每个人的发帖数超过总数的1/4，请找出这三个水王ID

 

思路：很明显，这次我们需要三个类似于candidate和三个类似于nTimes的变量，现在问题的关键是这三个nTimes为0和不为0该如何处理。

 

void findMaxId(Type * arr,int N,Type candidate[3]){  //candidate数组由main函数创建好传入    int nTimes[3],i,j;    bool flag;    for(i = 0; i < N; i++){        //flag用于标识candidate数组中的三个值有没有和arr[i]相同的        //如果有那么flag置为true，并跳出j循环，进入下一个i循环        //如果没有那么flag依旧为        flag = false;        for(j = 0; j < 3; j++){            if(arr[i] == candidate[j]){                nTimes[j]++;                flag = true;                break;            }        }        if(!flag){            //在flag为false时有三种情况，一种是nTimes中的3个值均为0，这时要重新设定candidate            //一种是nTimes中3个值均不为0，这时nTimes分别减1            //还有一种是个别nTimes值为0，这时要重新设置nTimes为0对应的candidate            if(nTimes[0] && nTimes[1] && nTimes[2]){                nTimes[0]--;                nTimes[1]--;                nTimes[2]--;            }            for(j = 0; j < 3; j++){                if(nTimes[j] != 0)                    continue;                else{                    candidate[j] = arr[i];                    nTimes[j] = 1;                    break;                }            }        }    }}

4.寻找N个数中最大的K个数

 

思路一：快速排序或堆排序，时间复杂度为Nlog(N)，然后取出最大的K个数，总的时间复杂度为O(N*log(N))+O(K)=O(N*log(N))；

思路二：我们只要找出最大的K个数，其余N-K个元素没必要进行排序，所以我们可以用交换排序或选择排序得到最大的K个元素，时间复杂度为O(N*K)；

上面两种方法要根据log(N)和K的大小来选择；

思路三：快速排序可以把原数组分为两部分，一部分比所选的数要大，一部分要比所选的数要小，设这两部分分别为Sa和Sb，如果Sa的长度大于K，那么我们从Sa中找出最大的K个数；如果Sa的长度小于K，设为M，那么Sa中的数是我们要的，同时还要从Sb中找出K-M个数。这样我们就把原问题分成了两个子问题。这样递归解决的时间复杂度为O(N*logK)。

伪代码：

 

maxK(S,k):    if(k <= 0)        return []    if(S.length < k)        return S    [Sa,Sb] = partition(S)    return maxK(Sa,k).Append(maxK(Sb,k - Sa.length))partition(S):    p = S[1]    for i in [2:S.length]:        S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i])    Sa.length < Sb.length ? Sa.Append(p) : Sb.Append(p)    return [Sa,Sb]

用快速排序的思路找到第K大的元素：

 

 

int partition(int arr[],int begin,int end){    int x = arr[begin];    int i = begin,j = end + 1;    while(1){        //i指向的肯定是比x要小的，j指向的肯定是比x要大的        while(arr[++i] > x);        while(arr[--j] < x);        if(i >= j)            break;        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }    //因为j指向的肯定比x要大，所以就把它和x交换了    a[l] = a[j];    a[j] = x;    return j;}int random_partition(int arr[],int begin,int end){    int i = begin + rand()%(end - begin + 1);    int temp = a[begin];    a[begin] = a[i];    a[i] = temp;    return partition(arr,begin,end);}int random_select(int arr[],int begin,int end,int k){    if(begin == end)    //递归结束        return arr[begin];    int index = random_partition(arr,begin,end);    int tempK = index - begin + 1;    if(tempK == k){ //找到第K大的元素        return arr[index];    }    elseif(temp > k){        return random_select(arr,begin,index - 1,k);    }else{        return random_select(arr,index + 1,end,k - tempK);    }}

思路四：上述几种方法的共同点都是对所有的数据需要访问多次，那么如果N特别特别大，达到百亿级别时该如何做呢，这个时候数据不可能完全放入内存，所以要尽量减少遍历的次数。此时我们可以维护一个大小为K的小根堆，根元素就是这K个元素中最小的一个，每次从N个元素中取出一个与它比较，如果比它小那么就舍弃，如果比它大就替换根元素，并调整小根堆，让根元素一直是最小的。调堆的过程时间复杂度为O(logK)，总的时间复杂度为O(N*logK)。如果内存不能完全放下K个元素，那么我们可以先找到最大的K' 个元素，然后找次大的K' 个元素，我们需要遍历N个元素 K/K' 取上整次。

 

思路五：对于特殊情况的N个数会有特殊的解法，如果这N个整数都是正整数，并且在一定的取值范围内，那么我们找到其中最大的一个MAX，然后建立一个数组arr[MAX]，下标为i的数组元素中存放的是元素i在N个数中出现的次数，我们扫描一次就可以得到该数组，这样我们就可以找到第K大的元素。

5.最大公约数

求两个整数的最大公约数。

思路一：设这两个数分别为X和Y，k = X/Y；b = X%Y；则X = k * Y + b；如果X和Y的最大公约数为Z，那么b必然可以被Z整除。f(X,Y) = f(Y,X%Y)；当其中一个数为0时，另一个数就是最大公约数。

 

int gcd(int X,int Y){    if(Y == 0)        return X;    else        return gcd(Y,X%Y);}

思路二：思路一的弊端在于需要用到取模运算，对于大整数而言，这是非常严重的开销，是整个算法的瓶颈，所以我们要想别的办法避免取模运算。我们发现X和Y的最大公约数为Z，那么X-Y一定可以被Z整除，即f(X,Y) = f(X-Y,Y)，如果X-Y小于Y，那么f(Y-X,Y)；

 

 

int gcd(int X,int Y){    if(Y == 0)        return X;    else        return (X > Y) ? gcd(X-Y,Y) : gcd(Y-X,Y);}

思路三：思路二的弊端在于当X和Y的值相差非常大时，会多次迭代减法运算，造成很大的开销。我们观察：

 

如果X,Y均为偶数，那么2一定是它们的公约数，f(X,Y) = f(X >> 1, Y >> 1)；

如果X或Y为偶数，那么2只能是其中一个的约数，设X为偶数，f(X,Y) = f(X >> 1, Y)；

如果X与Y均为奇数，那么X-Y是偶数，就可以归结为上一种情况，f(X,Y) = f(X,X-Y)；

 

int gcd(int X,int Y){    if(Y == 0)        return X;    else if(!(X & 0x1) && !(X & 0x1))        return  gcd(X >> 1, Y >> 1);    else if((X & 0x1) && (X & 0x1))        return (X > Y) ? gcd(X-Y,Y) : gcd(Y-X,Y);    else        return (X & 0x1) ? gcd(X >> 1,Y) : gcd(X,Y >> 1);}

 

6.寻找数组中的最大值和最小值、最大值和次大值

①求最大值和最小值

思路一：用两个变量MAX和MIN分别存放最大值和最小值，遍历数组，每个数分别与MAX和MIN比较，如果大于MAX或小于MIN就分别重置MAX或MIN，这样需要比较2N次；

思路二：用两个变量MAX和MIN分别存放最大值和最小值，成对取出数组中的数A和B，比较A和B，找到较小者（设为A），将A和MIN比较，将B和MAX比较，如果需要重置MAX或MIN则重置之，这样需要比较1.5N次；

思路三：分治法，将数组分为两部分，求出前一部分的最大和最小值，再求出后一部分的最大和最小值，然后综合起来求总体的最大值和最小值。这是个递归的过程。

 

void MaxAndMin(int A[],int begin,int end,int &Max,int &Min){    if(begin == end){        Max = Min = A[begin];        return;    }    if(begin + 1 == end){        if(A[begin] > A[end]){            Max = A[begin];            Min = A[end];        }else{            Min = A[begin];            Max = A[end];        }        return;    }    int mid = begin + (end - begin)/2;    int leftMax = 0;    int leftMin = 0;    MaxAndMin(A,begin,mid,leftMax,leftMin);    int rightMax = 0;    int rightMin = 0;    MaxAndMin(A,mid,end,rightMax,rightMin);    Max = (leftMax > rightMax) ? leftMax : rightMax;    Min = (leftMin < rightMin) ? leftMin : rightMin;}

我们来分析一下比较次数f(N)，N为数组长度：

 

f(2) = 1

f(N) = 2 * f(N/2) + 2 = 2 * ( 2 * f(N/4) + 2) + 2 = 2^2 * f(N/4) + 2^2 + 2 = 2^3 * f(N/8) + 2^3 + 2^2 + 2 = 2^k * f(N/(2^k)) + 2^k + ... + 2^2 + 2 （k = logN - 1）= 1.5N-2

由此可见，分治法总的比较次数并未减少

②求最大值和次大值

利用分治法和上例方法类似，只不过有一个地方需要注意：

先求出左边的最大值leftmax和次大值leftsecond，再求出右边的最大值rightmax和次大值rightsecond，然后合并，如何合并呢？分情况考虑：

1 如果leftmax > rightmax，那么可以肯定leftmax是最大值，但次大值不一定是rightmax，但肯定不是rightsecond，只需将leftsecond与rightmax做一次比较即可。

2 如果rightmax > leftmax，那么可以肯定rightmax是最大值，但次大值不一定是leftmax，但肯定不是leftsecond，所以只需将leftmax与rightsecond做一次比较即可。