O*2
发帖数: 178 | 1 给你一个数列，不知道长度，一个一个给，其中一个数出现次数超过半数
（如果数列长度2N+1，这个数出现不少于N+1，但是N事先未知）
怎么样找出这个数？
似乎听说过这个题，有提示吗？多谢 |
r*******y
发帖数: 1081 | 2 if the range of the numbers known, then hash can be used ?
【在 O*2 的大作中提到】
: 给你一个数列，不知道长度，一个一个给，其中一个数出现次数超过半数
: （如果数列长度2N+1，这个数出现不少于N+1，但是N事先未知）
: 怎么样找出这个数？
: 似乎听说过这个题，有提示吗？多谢
|
g**********y
发帖数: 14569 | 3 似乎只能把所有数都用hashtable保存下来吧。
不管你现在看见些什么数，到最后，每一个出现过的数，甚至还没出现的数，都有可能
是正确答案。 |
s*****n
发帖数: 5488 | 4 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 的大作中提到】
: 给你一个数列，不知道长度，一个一个给，其中一个数出现次数超过半数
: （如果数列长度2N+1，这个数出现不少于N+1，但是N事先未知）
: 怎么样找出这个数？
: 似乎听说过这个题，有提示吗？多谢
|
g**********y
发帖数: 14569 | 5 赞
【在 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**********y
发帖数: 14569 | 6 hint:思路类似一个array所有的数even只有一个是odd.
那是什么题？ |
s*****y
发帖数: 897 | 7 我就记得是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**e
发帖数: 6127 | 8 一个array所有数都出现偶数次，只有一个出现奇数次，要找到这个数。XOR可解。
当然如果这个数是0，那就只能vote了
【在 g**********y 的大作中提到】
: hint:思路类似一个array所有的数even只有一个是odd.
: 那是什么题？
|
g**********y
发帖数: 14569 | 9 哦，我还奇怪，要是只有一个奇数，把它找出来，还需要什么vote呢?
【在 g**e 的大作中提到】
: 一个array所有数都出现偶数次，只有一个出现奇数次，要找到这个数。XOR可解。
: 当然如果这个数是0，那就只能vote了
|
d*******d
发帖数: 2050 | 10 如果是0的话,也不用vote,最后xor结果就是0阿.
【在 g**e 的大作中提到】
: 一个array所有数都出现偶数次，只有一个出现奇数次，要找到这个数。XOR可解。
: 当然如果这个数是0，那就只能vote了
|
|
|
h*********n
发帖数: 11319 | 11 同疑惑
【在 d*******d 的大作中提到】
: 如果是0的话,也不用vote,最后xor结果就是0阿.
|
x******2
发帖数: 546 | 12 不用hash，线性扫一遍就行了。
每次舍弃2个不同的数，因为那个数超过半数，所以最后剩下的必然是所求
【在 O*2 的大作中提到】
: 给你一个数列，不知道长度，一个一个给，其中一个数出现次数超过半数
: （如果数列长度2N+1，这个数出现不少于N+1，但是N事先未知）
: 怎么样找出这个数？
: 似乎听说过这个题，有提示吗？多谢
|
g**e
发帖数: 6127 | 13 我的理解是你不知道最后结果是0，还是array里根本没有出现奇数次的数字。这个逻辑
严密
的程序应该是能给出判断的
【在 h*********n 的大作中提到】
: 同疑惑
|
O*2
发帖数: 178 | 14 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*2
发帖数: 178 | 15 thx
【在 x******2 的大作中提到】
: 不用hash，线性扫一遍就行了。
: 每次舍弃2个不同的数，因为那个数超过半数，所以最后剩下的必然是所求
|
O*2
发帖数: 178 | 16 如果没有出现奇数次的数，那么总数应该是偶数，如果有的话且xor结果为零，
那么这个数就应该是零
【在 g**e 的大作中提到】
: 我的理解是你不知道最后结果是0，还是array里根本没有出现奇数次的数字。这个逻辑
: 严密
: 的程序应该是能给出判断的
|
e******s
发帖数: 38 | 17 请问
如果没有任何一个数超过一半，这个算法是不是有可能随便返回一个出现次数很少的数？
【在 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])
|
