有一个数在一个数组中出现50%以上,让你在O(n)的时间内,O(1)的空间复杂度,找出那个数,其中数组内的数都是随机数,但是有范围。

2011-03-05 09:31:52

4 Answers

其实,有点像一个罐子里,有黑色白色两种球,白色的球超过一半,用什么办法去拿球,能保证最后留下的那个球是白色的。解决方案是,每次拿两个球,如果颜色一样就放回去,如果颜色不一样就都丢出来。
这个题目,可以采用类似的方法,每次取两个数,相同就保留,不同就都去掉。
具体实现过程中需要两个临时变量,一个记录候选结果,一个记录在扫描过程中出现的次数。 

times = 0. for i < N if times == 0 candidate = arr[i], times = 1 else if candidate == arr[i] times++ else times-- end if-else end if-else end for

最后,其实这个题是个经典面试题了,就在编程之美的129页。以上伪码显示不太好,可以直接翻书去了~
= =

2011-03-05 11:52:00

如果是50%以上,也就是出现次数最多的数字,问题归结为mode,同时保证时间复杂度O(N)和空间复杂度O(1)有难度。采用hashmap处理,时间复杂度O(N),空间复杂度O(N);如果先做一次排序操作,然后类似查找最长平台,空间复杂度可以降低到O(1),但是时间复杂度相应的会提高到O(n (log n ))。 期待时间复杂度O(N)和空间复杂度O(1)的算法。

2011-03-05 13:04:38

从任何一个地方将整个数组截断,分成前、后两部分的话,对于出现次数超过50%的数来说:要么前面出现超过50%,要么后面出现超过50%(要么都超过)。(1)

也就是说:如果存在一个位置,使得这个位置之前,不存在任意一个数,使得它的出现次数超过当前的50%;那么这个位置之后,一定存在一个数出现超过50%,而且这个数就是要求的数。(2)

再其次:如果前N个数中间,刚好有一个数出现了N/2次(N为偶数),那么满足了(2)的前提条件,只要求之后的数中出现次数超过50%的即可。(3)

最后:如果只有一个数,那这个数就是要求的答案。(4)

代码上面有人给了:

  
int over = 0, current = 0; for(int i = 0; i < N; i++) { if(over == 0) //说明current这个数出现的次数刚好为50%(或者算法刚开始),从现在开始重新开始;如果只有一个数的话,第一个即为所求,因此第一个就是当前的候选 { current = a[i]; over = 1; } else if(current == a[i]) //current这个数又多出现了一次;over表示current目前比其他数的总和多出现了多少次,如果over == 0那么说明current只出现了刚好50%。 { over++; } else //出现了一个不是current的数 { over--; } } //current即为所求
2011-03-05 15:04:23

先排序,然后中间的那个数肯定是出现概率大于50%的那个数了

2011-03-05 16:41:20
您不能回答该问题或者回答已经关闭!

相关文章推荐

  • C#开发中的反射机制

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

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

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

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

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

  • C#协变和逆变

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

  • C#运行时相互关系

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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