问题:给定一个数组,输出各元素出现的次数。
目录
法一:逐个统计
法二:用数组以值代址
法三:先排序,再进行统计
法四:利用哈希表进行统计
法一:逐个统计
思路:
数组第一个数为目标,遍历数组进行统计,统计后的数据替换成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;//数组是否全部为0
while (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。文章来源:https://www.toymoban.com/news/detail-810258.html
#include<iostream>
#include<unordered_map>//这里为了降低时间复杂度而使用的unorder_map
using 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]
{ //则把对应的值加1
record[arr[i]] += 1;
}
else //如果record未记录arr[i]
{ //则把arr[i]作为键插入record中,并把对应的值记为1
record[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.toymoban.com/news/detail-810258.html
到了这里,关于【C/C++】统计数组各元素个数的四种方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!