统计不同数字的个数(升级版)

我就是我 2023-10-06 17:06 49阅读 0赞

## 统计不同数字的个数(升级版) ##

此处用的是C++。

### 使用如下O(n2)级别的算法（普通版） ###

此处先是求出相同的个数，再用总的去减。

#include<iostream>
    using namespace std;
    
    int main()
    {
        int i,j,n,a[100005],sum=0;
        cin>>n;
        for(i=0; i<n; i++)
        {
            cin>>a[i];
        }
        for(i=0; i<n; i++)
        {
            for(j=1+i; j<n; j++)
            {
                if(i!=j&&a[i]==a[j])
                {
                    sum++;
                    break;
                }
            }
        }
        cout<< n-sum <<endl;
    }

![在这里插入图片描述][20210328102445726.png]

--------------------

### 使用如下O(n)级别的算法（升级版） ###

利用稀疏数组的办法：

#include<iostream>
    using namespace std;
    
    int main()
    {
        int i,n,m,s=0,a[100005]={0};
        cin >> n;
        for(i=0;i<n;i++)
        {
            cin >> m;
            if(a[m]==0)s++;
            a[m]=1;
        }
        cout << s << endl;
    }

原理如图：（拿长度为8的数组演示）

一开始![在这里插入图片描述][20210328102250797.png]  
先输入5（回车）

5 5 1 3 4（5有一个重复，应输出4）  
![在这里插入图片描述][20210328102409966.png]  
第一个为5，a\[5\]等于0，s+1，a\[5\]=1;

第二个为5，a\[5\]不等于0，s不变，a\[5\]=1;  
![在这里插入图片描述][20210328102323734.png]  
第三个。。。。。。以此类推

### 纯属个人笔记，若发现错误，请及时指出！！ ###

[20210328102445726.png]: https://img-blog.csdnimg.cn/20210328102445726.png
[20210328102250797.png]: https://img-blog.csdnimg.cn/20210328102250797.png
[20210328102409966.png]: https://img-blog.csdnimg.cn/20210328102409966.png
[20210328102323734.png]: https://img-blog.csdnimg.cn/20210328102323734.png