Guest Editor Needed - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>EB23 - 劳工卡

Guest Editor Needed

Guest Editor Needed# EB23 - 劳工卡

O*22013-05-12 07:05

1 楼

给你一个数列，不知道长度，一个一个给，其中一个数出现次数超过半数
（如果数列长度2N+1，这个数出现不少于N+1，但是N事先未知）
怎么样找出这个数？
似乎听说过这个题，有提示吗？多谢

c*g2013-05-12 07:05

2 楼

需要2-3个guest editors for a special issue of a Journal. Backgroud需要是和
sensor 还有nanomaterial有关系的。如果有兴趣，请站内。谢谢。

r*y2013-05-12 07:05

3 楼

if the range of the numbers known, then hash can be used ?

【在 O*2 的大作中提到】

: 给你一个数列，不知道长度，一个一个给，其中一个数出现次数超过半数
: （如果数列长度2N+1，这个数出现不少于N+1，但是N事先未知）
: 怎么样找出这个数？
: 似乎听说过这个题，有提示吗？多谢

g*s2013-05-12 07:05

4 楼

已发信给您
请查阅！

【在 c***g 的大作中提到】

: 需要2-3个guest editors for a special issue of a Journal. Backgroud需要是和
: sensor 还有nanomaterial有关系的。如果有兴趣，请站内。谢谢。

g*y2013-05-12 07:05

5 楼

似乎只能把所有数都用hashtable保存下来吧。
不管你现在看见些什么数，到最后，每一个出现过的数，甚至还没出现的数，都有可能
是正确答案。

T*72013-05-12 07:05

6 楼

正在给你发信，请查收，谢谢。

需要2-3个guest editors for a special issue of a Journal. Backgroud需要是和
sensor 还有nanomaterial有关系的。如果有兴趣，请站内。谢谢。

【在 c***g 的大作中提到】

: 需要2-3个guest editors for a special issue of a Journal. Backgroud需要是和
: sensor 还有nanomaterial有关系的。如果有兴趣，请站内。谢谢。

s*n2013-05-12 07:05

7 楼

majority voting algorithm
int MajorityVoting(int arr[], int n)
{
int majority;
int count = 0;
for (int i = 0; i < n; i++)
{
if (count > 0)
{
if (majority == arr[i])
count++;
else
count--;
}
else
{
count ++;
majority = arr[i];
}
}
return majority;
}
hint:思路类似一个array所有的数even只有一个是odd.

【在 O*2 的大作中提到】

C*r2013-05-12 07:05

8 楼

已发信给您，请查收。非常感谢！

【在 c***g 的大作中提到】

: 需要2-3个guest editors for a special issue of a Journal. Backgroud需要是和
: sensor 还有nanomaterial有关系的。如果有兴趣，请站内。谢谢。

g*y2013-05-12 07:05

9 楼

赞

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

: majority voting algorithm
: int MajorityVoting(int arr[], int n)
: {
: int majority;
: int count = 0;
: for (int i = 0; i < n; i++)
: {
: if (count > 0)
: {
: if (majority == arr[i])

g*y2013-05-12 07:05

10 楼

hint:思路类似一个array所有的数even只有一个是odd.
那是什么题？

s*y2013-05-12 07:05

11 楼

我就记得是UT Austin发明的，死活想不起名字了，多谢提醒
这里还有demo
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

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

: majority voting algorithm
: int MajorityVoting(int arr[], int n)
: {
: int majority;
: int count = 0;
: for (int i = 0; i < n; i++)
: {
: if (count > 0)
: {
: if (majority == arr[i])

g*e2013-05-12 07:05

12 楼

一个array所有数都出现偶数次，只有一个出现奇数次，要找到这个数。XOR可解。
当然如果这个数是0，那就只能vote了

【在 g**********y 的大作中提到】

: hint:思路类似一个array所有的数even只有一个是odd.
: 那是什么题？

g*y2013-05-12 07:05

13 楼

哦，我还奇怪，要是只有一个奇数，把它找出来，还需要什么vote呢?

【在 g**e 的大作中提到】

: 一个array所有数都出现偶数次，只有一个出现奇数次，要找到这个数。XOR可解。
: 当然如果这个数是0，那就只能vote了

d*d2013-05-12 07:05

14 楼

如果是0的话,也不用vote,最后xor结果就是0阿.

【在 g**e 的大作中提到】

: 一个array所有数都出现偶数次，只有一个出现奇数次，要找到这个数。XOR可解。
: 当然如果这个数是0，那就只能vote了

h*n2013-05-12 07:05

15 楼

同疑惑

【在 d*******d 的大作中提到】

: 如果是0的话,也不用vote,最后xor结果就是0阿.

x*22013-05-12 07:05

16 楼

不用hash，线性扫一遍就行了。
每次舍弃2个不同的数，因为那个数超过半数，所以最后剩下的必然是所求

【在 O*2 的大作中提到】

g*e2013-05-12 07:05

17 楼

我的理解是你不知道最后结果是0，还是array里根本没有出现奇数次的数字。这个逻辑
严密
的程序应该是能给出判断的

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

: 同疑惑

O*22013-05-12 07:05

18 楼

thx

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

: majority voting algorithm
: int MajorityVoting(int arr[], int n)
: {
: int majority;
: int count = 0;
: for (int i = 0; i < n; i++)
: {
: if (count > 0)
: {
: if (majority == arr[i])

O*22013-05-12 07:05

19 楼

thx

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

: 不用hash，线性扫一遍就行了。
: 每次舍弃2个不同的数，因为那个数超过半数，所以最后剩下的必然是所求

O*22013-05-12 07:05

20 楼

如果没有出现奇数次的数，那么总数应该是偶数，如果有的话且xor结果为零，
那么这个数就应该是零

【在 g**e 的大作中提到】

: 我的理解是你不知道最后结果是0，还是array里根本没有出现奇数次的数字。这个逻辑
: 严密
: 的程序应该是能给出判断的

e*s2013-05-12 07:05

21 楼

请问
如果没有任何一个数超过一半，这个算法是不是有可能随便返回一个出现次数很少的数？

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

: majority voting algorithm
: int MajorityVoting(int arr[], int n)
: {
: int majority;
: int count = 0;
: for (int i = 0; i < n; i++)
: {
: if (count > 0)
: {
: if (majority == arr[i])