关于众数问题，求助。另附一个Amazon题目求问。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于众数问题，求助。另附一个Amazon题目求问。

关于众数问题，求助。另附一个Amazon题目求问。# JobHunting - 待字闺中

i*72012-03-30 07:03

1 楼

How to find if a number is present >= (n / 2) times in an array of size
n?
关于这个题目，有没有时间复杂度是O(n)，空间复杂度是O(1)的解？
另外还有一题：
一百万个amazon product id，问过去一小时销售量top 10的id。

s*r2012-03-30 07:03

2 楼

MapReduce would be a more scalable solution. For more information, please
refer to the introduction to Hadoop or other MapReduce tutorials:
http://developer.yahoo.com/hadoop/tutorial/module4.html
---------------------------------------------------------
http://www.mitbbs.com/article_t/JobHunting/32078421.html
4.bar raiser: 一百万个amazon product id，问过去一小时销售量top 10的(map-
reduce)

s*n2012-03-30 07:03

3 楼

int number=a[0];
int count=1;
for (int i=1; iif (a[i]!=number) {
count--;
if (count==0) {
number = a[i];
count = 1;
}
} else count++;
}
return number;

i*72012-03-30 07:03

4 楼

这个只对绝对众数有效。也就是大于n/2的时候，但是等于n/2的时候，是无效的。

【在 s******n 的大作中提到】

: int number=a[0];
: int count=1;
: for (int i=1; i: if (a[i]!=number) {
: count--;
: if (count==0) {
: number = a[i];
: count = 1;
: }
: } else count++;

S*t2012-03-30 07:03

5 楼

Simple modification is to add another loop to check if there's a number
which has appeared [n/2] times.

【在 i*********7 的大作中提到】

: 这个只对绝对众数有效。也就是大于n/2的时候，但是等于n/2的时候，是无效的。

w*x2012-03-30 07:03

6 楼

第一题是微软的, 这题我感觉没啥意思.
第二题因该市每个product分散存储在很多台机器上, 每台机器对自己存储的product
id做hashing, hashing的结果发送到另外对应的机器上, 这样分散的product id就会只
聚集在特定目标机器上, 因为只有100万个product id是不是可以把所有统计出来的, count> pair 发送到同一台机器上, 因为只需要top 10, 所以不认为需要selection
algorithm或堆, 只需要用一个大小10的数组, 每次遍历这10个id对应的count,找出最
小的那个, 如果新的count大于最小的这个就替换它.

【在 i*********7 的大作中提到】

: How to find if a number is present >= (n / 2) times in an array of size
: n?
: 关于这个题目，有没有时间复杂度是O(n)，空间复杂度是O(1)的解？
: 另外还有一题：
: 一百万个amazon product id，问过去一小时销售量top 10的id。

s*n2012-03-30 07:03

7 楼

yes，run another loop that exclude this number and also count the number.
If the count>=n/2, then it's it; if countthe right answer by excluding another number.

【在 S******t 的大作中提到】

: Simple modification is to add another loop to check if there's a number
: which has appeared [n/2] times.

m*k2012-03-30 07:03

8 楼

take 2, if same, keep, otherwise discard both, keep doing until you can not
discard anyone.

【在 i*********7 的大作中提到】

: 这个只对绝对众数有效。也就是大于n/2的时候，但是等于n/2的时候，是无效的。

l*82012-03-30 07:03

9 楼

As iverson1407 said, the program doesn't work for the number that appears
exactly n/2 times when n is even.
Another problem: probably there is no such number existing in the array.
// Find the number(s) that appear
// Input:
// int * a, input array
// size_t n, length of the array
// Output:
/// int mode[2], store the mode nubmers found.
// return:
// int, how many mode numbers found. (0, 1 or 2)
//
int
FindModeNumber(int *a, size_t n, int modeNumbers[2])
{
if (n<2)
return n;
int count = 1;
int mode = a[0];
for (int i=1; iif(a[i] != mode)
if (--count == 0)
mode = a[i];
}
int modeCount = 0; // how many mode numbers found.
if (VerifyModeNumber(a, n, mode) )
modeNumbers[ modeCount++ ] = mode;
if (count == 1 && mode == a[n-1])
if (VerifyModeNumber(a, n, a[n-2]) )
modeNumbers[ modeCount++ ] = a[n-2];
return modeCount;
}
bool
VerifyModeNumber(int *a, size_t n, int mode)
{
int count=0;
for (int i=0; iif (a[i]==mode)
++count;
return count>= (n+1)/2;
}

【在 s******n 的大作中提到】

: int number=a[0];
: int count=1;
: for (int i=1; i: if (a[i]!=number) {
: count--;
: if (count==0) {
: number = a[i];
: count = 1;
: }
: } else count++;

b*d2012-03-30 07:03

10 楼

每次遍历还不如用堆，时间开销明显少很多。

每次遍历这10个id对应的count,找出最
小的那个, 如果新的count大于最小的这个就替换它.

【在 w****x 的大作中提到】

:
: 第一题是微软的, 这题我感觉没啥意思.
: 第二题因该市每个product分散存储在很多台机器上, 每台机器对自己存储的product
: id做hashing, hashing的结果发送到另外对应的机器上, 这样分散的product id就会只
: 聚集在特定目标机器上, 因为只有100万个product id是不是可以把所有统计出来的: , count> pair 发送到同一台机器上, 因为只需要top 10, 所以不认为需要selection
: algorithm或堆, 只需要用一个大小10的数组, 每次遍历这10个id对应的count,找出最
: 小的那个, 如果新的count大于最小的这个就替换它.