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

这篇具有很好参考价值的文章主要介绍了【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;//数组是否全部为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。

#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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++归并排序算法的应用:计算右侧小于当前元素的个数

    给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 示例 1: 输入:nums = [5,2,6,1] 输出:[2,1,1,0] 解释: 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元

    2024年02月06日
    浏览(37)
  • List移除元素的四种方式

    四种方式: 方式一,使用 Iterator ,顺序向下,如果找到元素,则使用 remove 方法进行移除。 方式二,倒序遍历 List ,如果找到元素,则使用 remove 方法进行移除。 方式三,正序遍历 List ,如果找到元素,则使用 remove 方法进行移除,然后进行索引 “自减”。 方式四,使用

    2024年02月14日
    浏览(38)
  • 最长上升子序列问题(LIS问题)与最长不上升子序列问题的四种方法(c++ 模板代码)

    最大上升子序列问题也叫做LIS问题,与最大公共子序列LCS问题是一类经典问题,在本章我们将总结一下求解 LIS最大上升子序列 的 几种方法 ,同时也会给出对应的 最大不上升子序列的求解方法。 关于LCS问题,我在后面会再出一篇博客来讲解, 废话不多说,我们直接进入正题

    2024年02月03日
    浏览(45)
  • java中数组的四种排序

    1.1数组的基本概念 数组(Array)是有序的元素序列。 若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量/12713827)。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计

    2024年02月15日
    浏览(53)
  • Java创建数组的四种方式

    1.使用默认值来初始化 语法: 数组元素类型 [] 数组名称 = new 数组元素类型 [数组长度] EG: int [] nums = new int [5]; //创建了一个类型为int,名字为nums ,长度为5的数组 2.先声明一个数组,再给值 语法: 数据元素类型 [] 数组名称; 数组名称 = new 数组元素类型[数组长度]; EG: int [] nums; num

    2024年02月09日
    浏览(64)
  • 针对常见的四种短路故障(单相接地短路,两相相间短路,两相接地短路,三相短路),可采取三种方法进行计算

    短路电流计算/ Matlab编程计算 针对常见的四种短路故障(单相接地短路,两相相间短路,两相接地短路,三相短路),可采取三种方法进行计算: 1.实用短路电流计算 2.对称分量法计算 3.节点导纳法计算 ID:16100 675647420588 用户_25948527

    2024年02月12日
    浏览(69)
  • Java创建数组、赋值的四种方式,声明+创建+初始化 详解

    以int数据类型为例 注意: new 数据类型[]{},其中花括号可以省去,但要在[ ]中填写数组的个数; 创建多维数组时 new后面第一个方括号中的元素数量不能省略 1、一维数组的声明方式: type[] arrayName; 或 type arrayName[]; 推荐使用第一种格式,因为第一种格式具有更好的可读性,表

    2024年04月11日
    浏览(58)
  • C语言指向二维数组的四种指针以及动态分配二维数组的五种方式

    当二维数组作为结构成员或返回值时,通常需要根据用户传递的参数来决定二维数组的大小,此时就需要动态分配二维数组。 如果现在有一个二维数组 a[3][2] ,那么将有以下几种指针可以指向它: 方式一 方式二: 在应用场景中通常采用以下三种方式动态分配二维数组,因为

    2024年02月04日
    浏览(56)
  • 【C++】C++的四种类型转换

    当等号两边的类型不同的时候、形参与实参类型不匹配的时候、返回值类型与接收返回值类型不一致时,就需要发生 类型转化 。 而类型转换又 分为隐式类型转换和显示类型转换 。 隐式类型转换是编译器在编译阶段自动进行,能转就转,不能转就编译失败。 而显示类型转换

    2023年04月09日
    浏览(53)
  • C++文件读取的四种方式

    C++可以根据不同的目的来选取文件的读取方式,目前为止学习了C++中的四种文件读取方式。 C++文件读取的一般步骤: 1、包含头文件 #includefstream 2、创建流对象:ifstream ifs (这里的ifs是自己起的流对象名字) 3、打开文件:file.open(\\\"文件路径\\\",\\\"打开方式\\\"),打开文件后并判断文件是

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包