d***a
发帖数: 316 | 1 给定一组共 n 个正整数，里面有重复的，要求找到重复出现频率最高的元素。这个频
率可能小于 0.5，所以找 median 的方法不行。 |
z*********n
发帖数: 203 | |
n*****g
发帖数: 82 | 3 这个是求majority,有一个recurvsive的算法，时间复杂度O(n)。这个算法可以对任意
的实数，不必非要整数。
【在 d***a 的大作中提到】
: 给定一组共 n 个正整数，里面有重复的，要求找到重复出现频率最高的元素。这个频
: 率可能小于 0.5，所以找 median 的方法不行。
|
P***P
发帖数: 1387 | |
d*****u
发帖数: 17243 | 5 可以建一个数组，元素的序号就是1到那些整数的最大值[1,max(X)]
然后遍历那个整数集，每次都对数组相应的位置做+1操作
完成以后求数组的最大值
这个方法是O(n)的
【在 d***a 的大作中提到】
: 给定一组共 n 个正整数，里面有重复的，要求找到重复出现频率最高的元素。这个频
: 率可能小于 0.5，所以找 median 的方法不行。
|
d********e
发帖数: 132 | 6 是什么算法？
【在 n*****g 的大作中提到】
: 这个是求majority,有一个recurvsive的算法，时间复杂度O(n)。这个算法可以对任意
: 的实数，不必非要整数。
|
P*******e
发帖数: 71 | 7 Hash. Key is the positive integer. Value is the times of every integer.
Just tranverse once to get the repeated elements with highest frequency.
O(n)
【在 d***a 的大作中提到】
: 给定一组共 n 个正整数，里面有重复的，要求找到重复出现频率最高的元素。这个频
: 率可能小于 0.5，所以找 median 的方法不行。
|
x*****p
发帖数: 1707 | 8 Hash may not always work. If n is very big and there are almost O(n)
distinct integers, then hash space is not enough. |
d***a
发帖数: 13752 | 9 假设这个每个数最多有K个bit。这个问题可以一个递归算法来解。设计一个递归函数
majority (S, k), S是整数集合，k是当前观察的bit位置。
1. 如果k=0, 数出S中bit 0分别是0和1的数目，返回两数之最大值。
2. 如果k>0, 按bit k等于0或1把S分为S0和S1，递归调用majority(S0,k-1)和majority
(S1,k-1)，取两个返回值中最大值，返回之。
最开始的调用是majority(Sn, K-1), Sn是输入整数集合。算法复杂度是O(N)，一共要
用K*N次比较。
这个算法是原创。:) 当然，应该是recreate the wheel。 |
