int main() { int a[7]={1,0,2,5,6,7,9}; Findnum(a,7); return 0; }

时间复杂度为O(log2n)。

10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。

//先对序列进行快速排序 //再进行一次遍历 //输出众数的重复次数

#include using namespace std;

int partions(int b[],int low,int high) {

int prvotkey=b[low]; b[0]=b[low]; while (low

while (low=prvotkey) --high;

b[low]=b[high];

while (low

b[high]=b[low]; }

b[low]=b[0]; return low; }

void qsort(int l[],int low,int high)

{

int prvotloc; if(low

{

prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序 由 prvotloc+1到 high

} }

void quicksort(int l[],int n) {

qsort(l,1,n); //第一个作为枢轴 ，从第一个排到第n个 }

int main() {

int a[10]={1,2,3,5,3,3,3,2,5,1}; int i=0;

int count=0;

int max=0;//max表示出现的次数

qsort(a,0,10); while(i<10) { int j; j=i+1; if(a[i]=a[j]&&i<10) { count++; i++; } if(count>max) { max=count; count=0; } }//while

cout<<\重复次数：\

return 0;

}

时间复杂度nlog(n)

11. 设M是一个n×n的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂性。

12. 设S是n（n为偶数）个不等的正整数的集合，要求将集合S划分为子集S1和S2，使得| S1|=| S2|=n/2，且两个子集元素之和的差达到最大。

//先用快速排序进行一趟排序

//如果s1（大的数集）的的个数大于n/2 //将（i<=n/2-low-1）个最小的数排到后面 //如果s1（大的数集）的的个数小于n/2 //将s2（小的数集）n/2-low-1排到前面 //将排好的数组的前n/2个数赋值给s1 //将排好的数组的后n/2个数赋值给s2

#include using namespace std; const int n=8;

void partions(int a[],int low,int high) { //进行一趟快排 int prvotkey=a[low]; a[0]=a[low]; while (low

while (low

a[low]=a[high];

while (low=prvotkey) ++low;

a[high]=a[low]; }

a[low]=prvotkey;

//如果s1（大的数集）的的个数大于n/2 if(low>=n/2) {

for(int i=0;i<=n/2-low-1;++i) {

for(int j=0;j

{ if(a[j]

//如果s1（大的数集）的的个数小于n/2 else

for(int i=0;i<=n/2-low-1;++i) {

for(int k=n-1;ka[k-1]) { int temp1=a[k]; a[k]=a[k-1]; a[k-1]=temp1; } }//for } }

int main() { int a[n]={1,3,5,9,6,0,-11,-8}; partions(a,0,n-1); for(int i=0;i

if(i<4) {

cout<<\属于子集s1的：\ cout<

cout<<\属于子集s2的：\ cout<