文档章节

找出出现次数站数据总数一半以上的数据

无情小白龙
 无情小白龙
发布于 2014/05/08 19:59
字数 392
阅读 106
收藏 6

假设数组类型为整形数组

  • 首先想到的思路是对每个出现过的数据进行个数统计,借助一个键值对集合,存放不同的数据及对应的出现的次数。出现次数大于N/2的即为要得到的结果。当数据量大的时候,会消耗空间。

  • 第二种思路是对已有的数据进行排序,排序之后相同的数据时连续的,又因为目标数据的出现次数大于N/2,所以下标在N/2的数据一定要找的数据。时间复杂度为O(N*logN)

  • 前两种思路要么要借助其他空间,要么时间复杂度高。下面介绍第三种思路。

    如果我们每次删除两个不同的数据,那么该数在剩余的数据中仍然占大于N/2的比例,通过不断的删除,把大的问题简化成小的问题,就可以简便的求解。


int calculate(int a[],int n)
{
        //target为要找的数据
	int target=0;
	int times=0;
	for(int i = 0;i<n;i++)
	{
	        //如果times为0,标志着前面的数据已删除,从剩下的数据中开始查找
		if(times==0)
		{
		        //将当前位置的数据假设为target
			target=a[i];
			times=1;
		}
		else
		{
			if(target==a[i])
			{
				times++;
			}
			else
			{
				times--;
			}
		}
	}
	return target;
}


参考书籍:《编程之美》


© 著作权归作者所有

无情小白龙
粉丝 4
博文 24
码字总数 12338
作品 0
西安
程序员
私信 提问
编程之美之寻找发帖“水王” 的算法问题

Tango是微软亚洲研究 院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每 个帖子。坊间风闻该“水王...

吟啸_徐行
2013/03/12
330
8
多个List集合元素进行比较,重复的元素进行记数

如 list1[3,4,5],list2[3,4,7],list3[3,6,7] 3重复的次数记为3 4重复的次数记为2,7重复的次数记为2; 由于集合的数量为3个,5,6数字只是出现一次,没有占集合总数的一半以上直接舍弃.使用JAVA如...

shanewds
2018/03/07
862
3
找出数列中个数大于总数一半的元素(编程之美2.3)

案例 数列3, 2, 3, 1, 3, 3, 2, 3中,3就是个数大于总数大于一半的元素。 思路一 对数列排序,再扫描一边,找出元素个数超过一半的元素。此时需要排序,同时需要记录每个元素出现个数,费时、...

技术mix呢
2017/11/08
0
0
29. 数组中出现次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,,5,4,2}.由于数字2在数组中出现了5次,超过数组长度的一半,因此输...

无精疯
2018/04/24
46
0
[剑指offer] 数组中出现次数超过一半的数字

本文首发于我的个人博客:尾尾部落 题目描述 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,...

繁著
2018/07/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Taro 兼容 h5 踩坑指南

最近一周在做 Taro 适配 h5 端,过程中改改补补,好不酸爽。 本文记录📝遇到的问题,希望为有相同需求的哥们👬节约点时间。 Taro 版本:1.3.9。 解决跨域问题 h5 发请求会报跨域问题,需...

dkvirus
56分钟前
4
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
今天
3
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
今天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
19
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部