C语言练习题之 数组中出现次数超过一半的数

2024-09-08 04:44

本文主要是介绍C语言练习题之 数组中出现次数超过一半的数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。

数据范围:n≤50000,数组中元素的值0≤val≤10000

要求:空间复杂度:O(1),时间复杂度O(n)

输入描述:

保证数组输入非空,且保证有解

示例1

输入:[1,2,3,2,2,2,5,4,2]

返回值:2

示例2

输入:[3,3,3,3,2,2,2]

返回值:3

示例3

输入:[1]

返回值:1

分析如下:

        题目意思比较明确,就是要找出数组中的一个数字,这个数字在数组中出现次数超过数组长度的一半。

        而题目提供的数组长度是≤50000,数组中元素的取值是 0 - 10000。

        基于这些信息,很容易从循环的角度出发,对数组每个数字进行循环统计。

代码如下:

//循环法查找
int find(int arr[], int sz)
{if (sz == 0)		//如果数组内没有元素,则返回-1。return -1;int i = 0;int j = 0;for (i = 0; i < sz; i++)	//遍历数组,每个数都查一遍{int count = 0;for (j = 0; j < sz; j++)	//数组中每个数与数组中其余数遍历一遍{if (arr[j] == arr[i] && i!= j)	//遍历过程中,与第i个数值相同,则计数+1,{count++;}if (count > sz / 2)	//当计数大于数组一半时,返回该数值。return arr[i];}}
}

        可以看到,循环法做起来很简单。但题目要求空间复杂度:O(1),时间复杂度O(n)。空间复杂度:O(1),即占用的内存空间不以数据量的变化而变化,无论多少数据,函数占用的内存是固定的;时间复杂度O(n),即花费的时间与数组元素成正比。

        上述解法中,空间复杂度满足,时间复杂度不满足,所以需要改进。之前我们介绍过用空间换时间的思路,即将所有可能的情况都列举出来,这里可以用一样的思路。

        根据题意,所求的返回值一定是 0-10000 这10001个数中的一个,所以如果提供一个容量为10001的数组,就可以把所求值的所有情况包含进去。然后遍历一遍即可。

代码如下:


int find(int arr[], int sz)
{if (sz == 0)		//如果数组内没有元素,则返回-1。return -1;int i = 0;int j = 0;int count[10001] = { 0 };	//题目中数组arr的取值范围是0-10000,则满足条件的数一定在这10001个数中//建立一个数组,包含10001个元素,对应arr数组中可能出现的10001种数值for (i = 0; i < sz; i++)	//遍历数组,对每种元素进行统计count[arr[i]]++;	//对arr数组中每种数值计数//如果arr数组中1出现了10次,则count[1]就是10;//5出现1000次,则count[5]就是1000;//假设n出现次数超出arr数组元素数一半,则n就是要找的值,即count[n] > sz/2for (i = 0; i < 10001; i++)	//遍历count数组{if (count[i] > sz / 2)	//找出满足条件的nreturn i;			//返回该值}
}

        这个思路可以算是穷举法。遍历过程中,arr数组中出现哪个数值,就对计数数组的对应位元素+1,统计出arr数组中每个数出现的个数,然后对技术数组遍历一遍,就能找到出现次数超过一半的数字了。

        这里空间复杂度是固定值,满足条件,时间复杂度是n+10001,也满足条件。但是占用空间过大,时间也较长,不符合实际,所以我们需要再优化。

        根据题意,所求的值 a 在数组中出现的次数一定是大于一半的。也就是说,如果对数组中的元素进行遍历,与 a 相同的数量减去与 a 不同的数量,结果一定大于0。

        那么我们假设一个 a ,从第一个数开始计算,与 a 相同则计数+1,不同则计数-1。若 a 是所求值,则最终结果大于0,返回 a;若 a 不是所求值,则将可能值赋给 a,继续计数,找到统计结果大于0的,就是所求值。

代码如下:

//优化解法
//前述解法占用内存空间太大,满足题目要求,但不符合实际。对其进行优化
//根据题意可以想到,返回值出现的次数比其余所有值出现的次数总和都多
//那么对数组元素进行计数,与返回值相同则数值+1,不同则数值-1
//因为返回值占总数一半以上,所以最后统计的数值一定大于0
//基于这个思路,从第一个元素开始计数,后一个元素与其不相等,则计数-1;相等则计数+1;
//当计数小于0时,则更换为新元素
//由于返回值占总数一半以上,所以其统计值最终必然大于0
int find(int* arr, int sz)
{if (sz == 0)	//如果数组内没有元素,则返回-1。return -1;int i = 0;int	count = 0;int a = arr[0];	//初始参考值设为数组第一个元素for (i = 0; i < sz; i++)	//遍历一遍,进行计数{if (arr[i] == a)	//第i个元素与参考值相同则计数+1count++;else				//第i个元素与参考值不相同时分项处理{if (count > 0)	//当之前计数大于0,则计数-1count--;else			//当之前计数为0,则将arr[i]赋值给参考值a,并计数为1{a = arr[i];count = 1;}}}return a;	//返回参考值
}
//可以看到,上述解法中,每个数值会统计一次,假设所求值是n
//参考值为n时,比较值为n, + 1,比较值为其他数, - 1;最后大于0
//参考值不为n时,比较值为n, - 1,比较值为其他数, + 1或 - 1;最后小于0,变为n,大于0
//占用内存少,且时间复杂度为O(n),满足题目要求

        可以看到,如果参考值是所求值 a,比较结束,最后结果大于0。如果参考值不是所求值 a,会被赋新值,因为所求值出现的总数最高,则遍历之后,最后 a一定会被赋值为所求值,比较结束后,结果也一定大于0。而大于0作为判断条件,就可以筛选出正确结果。

        这种解法的空间复杂度是固定值,且比较小,时间复杂度为n,满足题意。

        此方法细想容易绕晕,只要抓住核心,所求值 a 的数量占总数一半以上,就比较好理解了。以此核心为基础,在其为参考值时进行加法运算,其他数为参考值时进行减法运算,即可求得结果。

这篇关于C语言练习题之 数组中出现次数超过一半的数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147148

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、