编程之美系列02

时间:2022-01-28 09:56:43

     编程之美不断更新中,请各位看官多多提点,指正。废话不多说,直接上题:[QQ群: 189191838,对算法和C++感兴趣可以进来]

    觉得有用请按个赞哈!

     1、在一堆无序数组中,找出最大的K个数。

     显然,这样的题目我们可以通过排序解决,这样效率可以达到O(nlogn).当然也可以用快排,这样效率会更高些,毕竟只需要维护前K个数即可。

      那么还有没有更简单的呃方法呢?

     答案是显然的,我们想到堆排序,维护一个大小为K的小堆即可。堆排序的方法我们不必多讲了,本博客已经发过。直接上代码。

 1 void headAdjust(elemType *list,int j,int k){
2 int data=list[j];
3 for(int i=j*2+1;i<k;i=2*j+1){
4 if((i+1<k)&&(list[i]>list[i+1]))
5 i++;
6 if(list[i]<data){
7 list[j]=list[i];
8 j=i;
9 }else{
10 break;
11 }
12 }
13 list[j]=data;
14 }

    如果都为正整数,并且知道最大的那个数有多大,我们甚至可以开辟一个足够大的内存来存储。比如00000000010000010.表示出现了2,8两个数

    还有一种类似于开辟内存的就是开辟一个数组。比如int array[足够大];然后扫描两遍即可求出。

   2、最大公约数,求出两个数的最大公约数。

   充分利用公式: f(42,30)=f(30,12)=f(12,6)=f(6,0)=6

   那么可以通过递归的方式求解:

1 int gcd(int x,int y){
2 return !y?x:gcd(y,x%y);
3 }

    大家知道取余数的方式可能效率比较低下,这里尝试用减法的方式。

1 int gcd(int x,int y){
2 if(y==0)
3 return x;
4 if(x<y)
5 return gcd(y,x);
6 else
7 return gcd(x-y,y);
8 }

   再说一个简单的算法,斐波那契数列:f(n)=f(n-1)+f(n-2);当n=0,1是f(n)分别等于0,1;

    可以通过直接递归的方式求解:

1 int fib(int N){
2 if(N<=1)
3 return N;
4 else
5 return fib(N-1)+fib(N-2);
6 }

   test了一下,递归速度实在是无法忍受啊,因为他做了很多无用功,比如,f(N-2)会计算多次有没有。求f(N)的时候一次,f(N-1)的时候一次。而且每一次计算都是那么的龟速。我们可以保存他的计算结果,直接利用,这样速度会相当的快。请看下列算法:

1 int fib(int N){
2 int A[N];
3 A[0]=0,A[1]=1;
4 for(int i=2;i<=N;i++){
5 A[i]=A[i-1]+A[i-2]
6 }
7 return A[N];
8 }

   3、寻找数组中的最大数和最小数。

   这个题,我们一般都是通过保存两个数,一个保存最大,一个保存最小。并且通过后面的数,两两比较,大的那个数肯定不会是最小,小的那个肯定不会是最大的。如果不这样,每个数都要比较是不是最大,是不是最小,岂不是很不开心2N的时间复杂度哦。按照我的方式只需要1.5N的复杂度哈。

   感觉代码应该还有很多优化空间,求大神指教。

 1 void findMaxAndMin(elemType *list,int N){
2 assert(N>2);
3 elemType Max,Min;
4 if(list[0]>list[1])
5 Max=list[0],Min=list[1];
6 else
7 Max=list[1],Min=list[0];
8 for(int i=2;i<N;i+=2){
9 if(list[i]>list[i+1]){
10 if(list[i]>Max)
11 Max=list[i];
12 if(list[i+1]<Min)
13 Min=list[i+1];
14 }else{
15 if(list[i+1]>Max)
16 Max=list[i+1];
17 if(list[i]<Min)
18 Min=list[i];
19 }
20 }
21 cout<<Max<<" "<<Min<<endl;
22 }

 好的,上面这几个算法都是比较简单的了。讲一个稍微有一小点点分量的算法。

  4、计算两点之间的距离。

   两点,如果是在 在一维空间你是怎么做的呢?

   当然,我们可以通过简单的比较两两之间的距离,然后在得出最小的那个。是的,这种方式确实可以解决问题,但是你有没有发现这个效率比较底下呢?而且全都是乘法呢。

关于这方面的问题,我们应该第一步想到的就是排序,然后比较相邻两个点之间的距离就可以得到最小的是多少了。

   OK,一维空间的我们已经解决了,但是如果是二维呢?二维不可能只对X排序,然后比较X相近的两个点吧。当X相等的时候,距离也可以是很大的哦

   (首先要对X排序)但是其实我们可以借鉴一维空间的处理方式的。同时通过分治的方法解决,先找出各小部分的距离最小。我们可以分成两部分解决A,B(通过中心轴X来划分取X=M)。那么肯定最小距离只会出现在A最小,B最小或者A,B中各出现一个点。A(Mina),B(Minb)中的那个最小我们可以通过一个一个比较得到,但是如果两部分都有一点的时候是不是也可以一个一个计算,这样的时间复杂度是N/2*N/2.这里提供一种更为有效的方式,我们得到k=min(Mina,Minb).当A部分的点与X=M的距离大于k时,不考虑,同理当B部分的点与X=M的距离大于K时也不考虑,这样可以减少计算量。

   相信算法的思想都知道了,其实就是分治,然后再分别计算。

1 typedef double elemType;
2 struct point{
3 double x;
4 double y;
5 };
6 typedef point dataType;

    以下是算法主要过程:

 1 double theNearest(dataType *list,int left,int right){
2 if(left>=right)
3 return MaxNum;
4 if(right-left==1)
5 return Distance(list[left],list[right]);
6 double M=(list[left].x+list[right].x)/2;//把中间当做分界线,当然也可以通过其他方式选取
7 int k=findTheNum(list,left,right,M);//找到分界线左边第一个数,这里以x来划分
8 double leftMin=theNearest(list,left,k);//计算出左边那群点之间的最小距离
9 double rightMin=theNearest(list,k+1,right);//计算出右边那群点之间最小的距离
10 double Minest=leftMin<rightMin?leftMin:rightMin;//得出左右两边最小的点对
11 int leftCan=findLessM(list,left,k,M,Minest);//找到左边与M的距离在minest范围之类的所有点
12 int rightCan=findMoreM(list,k+1,right,M,Minest);//找到右边与M的距离在minest范围之类的所有点
13 double leftAndRight=countLeftRight(list,leftCan,k,k+1,rightCan);//计算左右两边在范围之类的最小值
14 return leftAndRight>Minest?Minest:leftAndRight;//最小值与minest比较,返回实际最小值
15 }

    以下是算法各方法实现。

 1 double countLeftRight(dataType *list,int leftCan,int leftEnd,int rightCan,int rightEnd){
2 double min=MaxNum;
3 for(int i=leftCan;i<=leftEnd;i++){
4 for(int j=rightCan;j<=rightEnd;j++){
5 double dist=Distance(list[i],list[j]);
6 if(min>dist)
7 min=dist;
8 }
9 }
10 return min;
11 }
12 int findLessM(dataType *list,int left,int k,double M,double min){
13 int i=k;
14 while(i>=left&&(M-list[i].x)>min)
15 i--;
16 return i;
17 }
18 int findMoreM(dataType *list,int k,int right,double M,double min){
19 int i=k;
20 while(i<=right&&(list[i].x-M)>min)
21 i++;
22 return i;
23 }
24 int findTheNum(dataType *list,int left,int right,double M){
25 for(int i=left;i<right;i++){
26 if(list[i].x<M&&list[i+1].x>M)
27 return i;
28 }
29 return 0;
30 }
31
32
33 double Distance(point A,point B){
34 double X=A.x-B.x;
35 double Y=A.y-B.y;
36 return X*X+Y*Y;
37 }

 排序算法:

 1 int paration(dataType *list,int left,int right){
2 dataType temp=list[left];
3 while(left<right){
4 while(left<right&&list[right].x>=temp.x)
5 right--;
6 list[left]=list[right];
7 while(left<right&&list[left].x<=temp.x)
8 left++;
9 list[right]=list[left];
10 }
11 list[left]=temp;
12 return left;
13 }
14
15 void quickSort(dataType *list,int left,int right){
16 if(left<right){
17 int i=paration(list,left,right);
18 quickSort(list,left,i-1);
19 quickSort(list,i+1,right);
20 }
21 }

 

    上面用的排序算法是快速排序,查找我没有用二分查找,实际上如果用二分查找的话速度可能会快一些,这里为什么说可能呢,因为毕竟两边的数都是逼近轴中心的。

      时间关系,代码没有进行过多的优化,出现BUG在所难免,有问题请大家批评指正。谢谢!

      

     版权所有,欢迎转载,但是转载请注明出处:潇一