面试算法整理.pdf

算法摘自：剑指offer，编程之美，C++编程关键路径，程序员求职宝典 1. 数组中出现次数超过一半的数字(剑指offer 29 题 编程之美 寻找发帖水王) 解法一：基于快排中分割算法的方法 数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序， 那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。 也就是说，这个数字是统计学上的中位数，即长度为n 的数组中第n/2 大的数 字。我们有成熟的O(n)算法得到数组中任意第k 大的数字。 这种算法是受快速排序算法的启发，在随机快排中，先随机选择一个数字，然 后将比它小的数字都放在它的左边，比它大的都放在它的右边。 如果调整好位置后，这个选中的数字的下标刚好是 n/2，那么这个数字就是数 组中的中位数。 如果它的下标大于 n/2，那么中位数应该在它的左边，可以接着在它的左边查 找；下标小于n/2 的情况类似，这是一个典型的递归过程。 当然，在这其中要考虑输入无效的情况（数组指针为NULL）；也要考虑如果输 入的数组中出现频率最高的数字并没有达到出现次数超过数组长度一半的情况。 #include stdio.h int Partition(int A[],int low,int high) { int pivot=A[low]; while(low high) { while(lowhigh A[high]=pivot) --high; A[low]=A[high]; while(lowhigh A[low]=pivot) ++low; A[high]=A[low]; } A[low]=pivot; return low; } int HalfData(int a[],int len) { int start=0; int end=len-1; int middle=len 1; int index=Partition(a,start,end); printf(index1:%d\n,index); while(index != middle) { if(index middle) { end=index-1; index=Partition(a,start,end); } else { start=index+1; index=Partition(a,start,end); } } return a[index]; } void main() { int a[9]={1,2,3,2,2,2,5,4,2}; int len=9; int result=HalfData(a,9); printf(result:%d,result); } 解法二：根据数组特点找出O(n)的算法 数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比 其他所有数字出现的次数的和还要多。 因此我们可以考虑用两个变量：一个保存一个数字，一个保存次数。 开始时，保存数组中第一个元素，次数设置为1； 遍历数组： 如果下一个数字和之前保存的数字相同，则次数递增1； 如果下一个数字和之前保存的数字不同，则次数递减1；