每日一练之排序算法(P1097 统计数字)

某次科研调查时得到了n个自然数，每个数均不超过1500000000(1.5×10^9)。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

采用sort直接排序，直接略过排序门槛；

 //P1097 统计数字

 #include<iostream>

 #include<algorithm>

 using namespace std;

 //const int MAX=200001;

 int main()

 {

     int i,n,count;

     cin>>n;

     int *a=new int[n];

     for(i=;i<n;i++)    cin>>a[i];

     sort(a,a+n);

     for(i=;i<n;i++)

     {

         count=;

         cout<<a[i]<<" ";

         while(a[i+]==a[i])  //如果后一位数相同，则统计叠加，否则输出统计结果

         {

             count++;i++;

         }

         cout<<count<<endl;

     }

     delete []a;

     return ;

 }

注：sort（start,end+1,排序方法)，start为排序起始地址，而end+1是指实际上是最后一个排序地址的下一个地址（为什么要+1呢？因为这样的设计是整个stl的设计原则决定的，STL的容器在传递迭代器参数时都是传递容器的开始位置，以及容器结尾的下一位置）；排序方法默认升序，也可重写，注意返回bool型或int型。

补上快排与堆排序的代码：

 void QuickSort(int a[],int left,int right)

 {

     if(left<right)

     {

         int i=Division(a,left,right);

         QuickSort(a,left,i-);

         QuickSort(a,i+,right);

     }

 }

 int Division(int a[],int left,int right)     //常用的找分界点方法

 {

     int temp=a[left];

     while(left<right)

     {

         while(left<right&&a[right]>=temp)  right--;

         a[left]=a[right];

         while(left<right&&a[left]<=temp)    left++;

         a[right]=a[left];

     }

     a[left]=temp;

     return left;

 }

 int Division(int a[],int left,int right)   //另一种方式，通过将小于等于基准值的数全部集中到基准点左侧，count值即为最终基准值所在序号

 {

     int t,temp=a[left];

     int count=left;

     for(int i=left+;i<=right;i++)

     {

         if(a[i]<=temp)

         {

             count++;

             t=a[i];

             a[i]=a[count];

             a[count]=t;

         }

     }

     t=a[left];

     a[left]=a[count];

     a[count]=t;

     return count;

 }

 ////////堆排

 void HeapSort(int a[],int n)

 {

     for(int i=n/-;i>=;i--)    HeapAdjust(a,i,n);

     for(int i=n-;i>;i--)

     {

         int t=a[];

         a[]=a[i];

         a[i]=t;

         HeapAdjust(a,,i);

     }

 }

 void HeapAdjust(int a[],int s,int n)

 {

     int j,temp;

     while(*s+<n)

     {

         j=*s+;

         if((j+<n)&&(a[j+]>a[j]))    j++;

         if(a[s]<a[j])

         {

             temp=a[s];

             a[s]=a[j];

             a[j]=temp;

             s=j;

         }

         else break;

     }

 }

最简短做法是使用map与set, 一个统计数，一个统计值；

 //#include<bits/stdc++.h>

 #include<iostream>

 #include<map>

 #include<set>

 using namespace std;

 int main() {

     map <int,int> num;

     set <int> a;

     int n,i,q;

     cin>>n;

     for(i=; i<=n; i++) {

         cin>>q;

         num[q]++;

         a.insert(q);

     }

     for(set<int>::iterator it=a.begin(); it!=a.end(); it++)

         cout<<*it<<" "<<num[*it]<<endl;

 }

巴特西

每日一练之排序算法(P1097 统计数字)

最新文章

热门文章