比如模型 [4, 1, 2, 2, 2, 3, 1] 中1的出现次数是2次。当数数组元素增加到30万左右的时候如何高效的计算出指定元素出现次数。大家有什么思路或算法可以分享下

2011-02-14 01:17:17

12 Answers

根据本题的特点是,如果数据量大了,可以把数据分割,进行多任务分治查询,但是如果是30万的数据量,不用分治应该就可以。

本题的出发点一定是查询多次的高效算法,否则如果仅仅是查询一次,最好的方法就是从头到尾顺序数,时间复杂度是O(N)(上面孙晋硕给出的方法)。

为了提高查询效率,一定要对原始数据建索引,建索引的时间一定大于等于O(N),建好索引后就可以提高查询算法的效率了,根据索引的不同,查询时间可以为O(LogN),也可以做到O(1)。下面给出两个具体的思路:
1.对数据排序是一种自然的思路,建索引的时间复杂度是O(NLogN),这样查询时使用二分法,查找的时间复杂度是O(LogN)。
2.使用Hash来记录统计结果,key是数组的值,value是该值出现的次数,这样建索引的时间复杂度是O(N),查询的时间复杂度是O(1)。

做为补充,在实际应用中,往往不但要给出某个值出现的个数,同时还要给出具体出现的位置。这个时候,索引结构不仅要考虑创建时的时间复杂度,还要考虑空间效率。具体的建索引的技巧比较多,就不在这里展开说了。

2011-02-14 02:51:14

o(n)的算法就是遍历一次就行了,遍历可以通过多线程来处理,将数组分成n等份,每个线程处理一份数据,然后把每个线程统计的结果累加起来就OK。

2011-02-14 04:30:36

根据我的理解:你的需求是不是有一个大数组,其中存在大量重复数据,需要反复给出一个特点值,获取其在数组中出现的次数?
如果是这样的话,我的基本思路是:先对数组进行预处理,用离散化的思路建立一个有序表,这样可以有效降低时空复杂度,且无视数据分布范围(具体方法后面描述),保存等于某个值的数的个数;查询的时候,采用二分法搜素。
既然能查询一个数出现了多少次,那么大多数情况下,数据都会有重复,即不同的数的个数小于数据个数。离散化是为了应对数据散布范围过大的问题,同时适用于浮点数。关于离散化不清楚的同学可以百度一下,基本思路是,只记录哪些有意义的点的值,排序后作为新的索引,举个简单的例子:在整数轴上任意画线段求重叠次数最多的部分,最简单的思路是记录各个点被画了几次,但数据范围大了(-10^9~+10^9),明显内存不够,此时可以只记录各个线段端点,排个序以原端点对应的下标为新端点,当然原来是多少要记录下来(就好像做了个不等比例的放缩,放缩到0到n,各个数据间隔1)。
本问题中数据散布未知,要建立索引应该用此方法。数据结构为
orderd-set of pair(key,count)
其中key表示原数据,count表示key的出现次数。orderd-set可以是任意可表示有序集合的数据结果(依据key排序),例如排序后的数据,排序二叉树,hash表(空间性能可能不好)等。
如果输入数组一经输入不在变化,建议使用排序后的数组作为容器,最省空间。
但是如果数组可能发生变化的话,建议使用有序树结构,它不仅可以在线建立,而且每次添加操作是O(log(n))的,n个输入数据总体上在O(nlog(n))时间内完成。空间复杂度为O(n)。

由于是有序集合,查找时可以在不超过O(log(n))的时间内完成,只有hash表可以在平摊时间O(1)内完成,但空间复杂度不保证。毕竟30万数据量还是较小,O(log(n))可以轻松查到,没有必要再拿大量的额外空间换少量的提升时间。当然如果你的查询特别密集除外。

C++代码(有采用序树):
假设数组为T input[len];//T可为任意数值类型
//建立,O(nlog(n)):
map<T,int> container;
for(int i=0;i<len;i++)
container[input]++;
//查询x,O(log(n)):
cout<<container[x];

2011-02-14 06:14:08

利用多线程 将数据平均分成若干份 大概每份= 数据数(本题30w)/cpu核数 创建cpu核数个线程同时查找指定元素 记录下出现的次数 然后得到每份中指定元素出现的次数 相加 就得到想要的结果了 这样的题目 明显不依赖于数据本身 循环操作也对数据无影响 所以用多线程 确实可以达到提速的效果 单核的cpu估计现在也很少见了 最起码也是双核的 速度不会提升一倍 但也会比单纯的顺序遍历一遍整个数据 快的多
希望可以帮到你

解释下 也不一定是真的要你申请变量去存储下分的那部分 既然有数据 看数据时链表形式存储的还是数组形式 给个指针就可以 然后有个分成的份数 如果是链表结构 或许该更加慎重些 不支持随机索引 会使复杂度增大 我觉得这道题叙述的详细些 会更有利于别人对他出谋划策 否则 任何结论都很片面
不过 如果不是支持随机存储的 我想只能用一个办法 那就是头尾各自起一个线程 然后有个记录下 数据量的一半num=数据个数/2 数据量是否为偶数pd=if((数据个数%2)== 0 ) 然后两个线程中分别到了num pd为true的话 两个线程统计结果相加即可 为false 则让其中一个多判断一次 然后 相加就是结果 !!当然这必须是双向链表 倘若单向 还是顺序执行吧

2011-02-14 08:16:11

我提供一个思路:你先把数分成多组,然后分别进行排序,再看起多个进程用二分法分别进行查找。

2011-02-14 09:29:55

具体问题具体分析。
如果你的模型里面的个体分布不广。可以才用一个1维数组来装,见一个就加1个。
打个比方。统计高考上线人数。
比如高考成绩处于0-750之间。开一个751的数组。遇到几分相应的数组加1.
遍历1遍就统计出来了。

如果你的模型,个体分布广,但个体总数不多。也可稍做变化,采用这样的思路。
但是如果分布广,总数又多的话。
这个方法就不合适了。

2011-02-14 11:29:04
您不能回答该问题或者回答已经关闭!

相关文章推荐

  • C#中using指令的几种用法

    using + 命名空间名字,这样可以在程序中直接用命令空间中的类型,而不必指定类型的详细命名空间,类似于Java的import,这个功能也是最常用的,几乎每个cs的程序都会用到

  • C#实例解析适配器设计模式

    将一个类的接口变成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够一起工作

  • 使用托管C++粘合C#和C++代码(二)

    本文实现一下C++代码调用C#代码的过程。我构造一个简单并且直观的例子:通过C++ UI 触发C# UI.

  • C#开发高性能Log Help类设计开发

    项目中要在操作数据库的异常处理中加入写Log日志,对于商业上有要求,写log时对其它操作尽可能影响小,不能因为加入log导致耗时太多

  • Async和Await使异步编程更简单

    C#5.0中async和await两个关键字,这两个关键字简化了异步编程,之所以简化了,还是因为编译器给我们做了更多的工作

  • C#开发中的反射机制

    反射的定义:审查元数据并收集关于它的类型信息的能力。元数据(编译以后的最基本数据单元)就是一大堆的表,当编译程序集或者模块时,编译器会创建一个类定义表,一个字段定义表,和一个方法定义表等

  • C#运行时相互关系

    C#运行时相互关系,包括运行时类型、对象、线程栈和托管堆之间的相互关系,静态方法、实例方法和虚方法的区别等等

  • C#协变和逆变

    “协变”是指能够使用与原始指定的派生类型相比,派生程度更大的类型,“逆变”则是指能够使用派生程度更小的类型

  • C#基础概念之延迟加载

    延迟加载(lazy load)是Hibernate3关联关系对象默认的加载方式,延迟加载机制是为了避免一些无谓的性能开销而提出来的,所谓延迟加载就是当在真正需要数据的时候,才真正执行数据加载操作

  • 使用托管C++粘合C#和C++代码(一)

    C#在xml读写,数据库操纵,界面构造等很多方面性能卓越;C++的效率高,是底层开发的必备武器

  • C#中的索引器的简单理解和用法

    C#中的类成员可以是任意类型,包括数组和集合。当一个类包含了数组和集合成员时,索引器将大大简化对数组或集合成员的存取操作

  • 深入C# 序列化(Serialize)、反序列化(Deserialize)

    C#中的序列化和反序列化,序列化是.NET运行时环境用来支持用户定义类型的流化的机制