【C/C++】统计数组各元素个数的四种方法

阅读本书更多章节>>>>

 问题：给定一个数组，输出各元素出现的次数。

目录

法一：逐个统计

法二：用数组以值代址

法三：先排序，再进行统计

法四：利用哈希表进行统计

---

法一：逐个统计

 思路：

数组第一个数为目标，遍历数组进行统计，统计后的数据替换成0（表示已删除），统计后输出数目。

优点：呃。。不需要明确指出数组的具体大小

缺点：时间复杂度较高，最高可达

//计数函数int COUNT(int* arr, int size, int tar,int pos) {int count = 0;for (int j = pos; j < size; j++){if (arr[j] == tar){arr[j] = 0;count++;}}return count;}void solution1(int * arr, int size) {int pos = 0;//记录查找起始位置，辅助确定查找目标int tar;    //记录查找目标bool flag = true;//数组是否全部为0while (flag){flag = false;//数组中无可统计元素for (pos = pos; pos < size; pos++) //检查数组是否全部为0{if (arr[pos] != 0) {tar = arr[pos];//记录查找目标flag = true;//数组中有可统计的元素cout << tar << "出现的次数为" << COUNT(arr,size,tar,pos) << endl;break;}}}}

法二：用数组以值代址

思路：

定义一个数组并全部初始化为零，用于计数。然后把arr中元素的值作为下标对计数数组进行访问。让其对应的值加一。

优点：算法执行速度大幅提升，时间复杂度为 n + size2

缺点：无法对较大的数据进行统计，容易越界访问，且空间复杂度会随着数据值的增大而增大。

#include<iostream>using namespace std;int test[50];//定义一个用来计数的数组void solution2(int* arr,int size1,int * test,int size2) {for (int i = 0; i < size1; i++) //遍历arr数组进行统计    {test[arr[i]]++;//用arr[i]的值作为下标对test进行访问}for (int i = 0; i < size2; i++) //输出    {if(test[i] != 0)cout << i << "出现的次数为" << test[i] << endl;}}int main() {int arr[20] = { 12,12,31,23,21,32,42,3,34,21,42,2,21,21,23,23,1,2,3,1 };solution2(arr, 20, test, 50);return 0;}

法三：先排序，再进行统计

原理：

先进行排序，后进行遍历计数。

排序后相同的元素都在一起，可通过相邻两个元素是否相等进行计数。

优点：算法效率较高，时间复杂度大概为nlogn + n

#include<iostream>#include<algorithm>#define end 100000 //作为排序后的最后一个元素防止下面代码出现越界访问using namespace std;void solution3(int * arr,int size){int count = 1; //定义一个变量用于计数sort(arr, arr + size); //排序for (int i = 0; i < size - 1; i++) //遍历排序后的arr数组    {if (arr[i] == arr[i + 1]) //如果相等，则count + 1        {count++;}else //否则输出个数，并将count重置为 1；        {cout << arr[i] << "出现的次数为" << count << endl;count = 1;} }}int main() {int arr[20] = { 12,2,3,23,1,4,12,3,12,12,32,4,24,32,42,1,2,1,1,end };solution3(arr, 20);return 0;}

法四：利用哈希容器进行统计

原理：

对法二的改进，利用哈希表的原理对数组中的元素进行统计。

把数组中的元素作为键存入哈希容器中，当再次遇到相同的元素时，可以通过键直接找到它所对应的值。

优点：可以对字符串数组进行统计，时间复杂度也较低，大致为n。

#include<iostream>#include<unordered_map>//这里为了降低时间复杂度而使用的unorder_mapusing namespace std;void solution4(int* arr, int size) {unordered_map<int, int> record;//创建一个哈希容器用来计数for (int i = 0; i < size; i++) //把数组中的数据作为键存入record    {if (record.count(arr[i])) //如果record已记录过arr[i]        {                         //则把对应的值加1record[arr[i]] += 1;}else     //如果record未记录arr[i]        {        //则把arr[i]作为键插入record中，并把对应的值记为1record[arr[i]] = 1;}}for (auto i : record) //遍历record容器    {cout << i.first << "出现的次数为" << i.second << endl;}}int main() {int arr[20] = { 1,2,7,2,1,1,4,2,2,2,2,2,1,1,2,2,3,4,3,3 };solution4(arr, 20);return 0;}

<大一小萌新原创文章，欢迎大佬指出错误，或提出更优的算法(◦˙▽˙◦)>

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-03-27/149264.html，文章来源：网络cs，作者：亙句，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！