两个等长的升序数组中，找出两个序列的中位数
思想：若a为A的中位数，b为B的中位数，若a=b，则就为两个数组的中位数，若a<b，则A舍弃左边，B舍弃右边,两边舍弃等长的部分，然后重新比较两个剩下部分的中位数，以此类推。
若a>b，则相反。
void SearchM(SqList &L1,SqList &L2){ int h1,h2,r1,r2; int m1,m2; r1=MaxSize-1; r2=MaxSize-1; h1=0; h2=0; while(h1!=r1||h2!=r2){ m1=(h1+r1)/2; m2=(h2+r2)/2; cout<<L1->data[m1]<<endl; cout<<L2->data[m2]<<endl; if(L1->data[m1]==L2->data[m2]){ cout<<L1->data[m1]; break; } if(L1->data[m1]<L2->data[m2]){ if((r1+h1)%2==0){ h1=m1; r2=m2; }//元素个数是奇数时,舍去中位数左边的值 else{ h1=m1+1; r2=m2; }//当元素个数是偶数时，舍去中位数及中位数左边的值 } if(L1->data[m1]>L2->data[m2]){ if((r2+h2)%2==0){ r1=m1; h2=m2; } else{ r1=m1; h2=m2+1; } } } if(L1->data[m1]<L2->data[m2]){cout<<L1->data[m1]<<endl;} else {cout<<L2->data[m2]<<endl;} }
找出数组中的主元素，即数组中一种元素最多的个数，若个数大于n/2（n为数组总数），则返回主元素，否则返回-1
思想：设计一个num和c，c为当前元素,num记录c是否为主元素，若下一个值与c不同，则num--，若num减为0，则当前的元素赋值给c，重新开始,num=1
最后确认c的真实个数，判断数组c是否为主元素
int MajorityNumber(SqList &L){ int count=1; int num=L->data[0];//记录数组中第一个值为初始元素，count为1 for(int i=1;i<MaxSize;i++){ if(num==L->data[i]){count++;} else {count--;} if(count==0){//若count减为0，则当前元素为num，重新开始 num=L->data[i]; count=1; } } count=0; for(int i=0;i<MaxSize;i++){ if(L->data[i]==num){count++;} }//最后判断num的真实个数 if(count>MaxSize/2){cout<<count<<endl;return 1;} else{cout<<"-1"<<endl;return -1;} }
原文：https://www.cnblogs.com/Yshun/p/11605011.html