5 冫御风

尚未进行身份认证

暂无相关简介

等级
TA的排名 62w+

找出数组中的主元素

问题:在一个规模为N的数组A[N]中,所谓主元素就是出现次数大于N/2的元素,例如 3.3.4.2.4.4.2.4.4  有一个主元素为4。          给出一个算法,如果过半元素存在,就找出来,否则给出报告,要求给出O(N)的算法。解答:1.如果确定数组中存在主元素,则有两种解法。一是用递归,遍历数组,第1步,如果元素的个数是1,算法退出,第2步,元素两两比较,如果

2015-04-20 14:35:46

如何在时间复杂度为O(n),空间复杂度为O(1)的条件下,统计数组中不同元素出现的次数

一个长度大小为n的数组,数组中的每个元素的取值范围在[1,n],且为正整数。问:如何在时间复杂度为O(n),空间复杂度为O(1)的条件下,统计数组中不同元素出现的次数。思路:数组按序扫描,通过当前元素的值作为下标,找到下一个元素。最后得到的数组中,下标(因为下标从0开始的,故输出时需要+1)为数组中出现的元素,每个下标对应的值取反输出即是该元素出现的频率。若当前元素小于0,  

2015-04-17 17:00:30

如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)

看上去似乎任何已知的算法都无法做到,如果谁做到了,那么所有的排序方法:QuickSort,ShellSort,HeapSort,BubbleSort等等等等,都可以扔掉了,还要这些算法干吗阿,呵呵。不过实际上,在数字范围有限制的情况下,是有一个这样的算法的,只需要用一个数组记录每个数字出现次数就可以了。假定你的数字范围在0到65535范围之内,定义一个数组count[65536](这个空间是常

2015-04-17 16:54:36
勋章 我的勋章
    暂无奖章