r****o
发帖数: 1950 | 1 这个是编程之美中的一题，有谁有比较好的解法吗?
一个int数组，其中有3个majority数，每个都超过数组总数1/4。怎么找出这3个数来。
比如说3 2 6 3 2 1 6 3 6 2 7， 这3个数就是3,2,6 | B*****t
发帖数: 335 | 2 每个数都超过数组总数1/4， 故3个数占了3/4以上，剩下的数只占1/4一下。
剩下的做法和n个数中有一个数的个数超过总数的1/2的道理一样
来。
【在 r****o 的大作中提到】
: 这个是编程之美中的一题，有谁有比较好的解法吗?
: 一个int数组，其中有3个majority数，每个都超过数组总数1/4。怎么找出这3个数来。
: 比如说3 2 6 3 2 1 6 3 6 2 7， 这3个数就是3,2,6
| r****o
发帖数: 1950 | 3 还是不懂。
能不能再详细一点 :>)
【在 B*****t 的大作中提到】
: 每个数都超过数组总数1/4， 故3个数占了3/4以上，剩下的数只占1/4一下。
: 剩下的做法和n个数中有一个数的个数超过总数的1/2的道理一样
:
: 来。
| l******c
发帖数: 2555 | 4 but in "一个数的个数超过总数的1/2", you only need find one number, and can
get the index by scan and counter, here, three numbers need to figure out
【在 B*****t 的大作中提到】
: 每个数都超过数组总数1/4， 故3个数占了3/4以上，剩下的数只占1/4一下。
: 剩下的做法和n个数中有一个数的个数超过总数的1/2的道理一样
:
: 来。
| s******i
发帖数: 44 | 5 如果扫描数组一次，建立一个类似hashtable的结构，那所有类似问题都能解决了，是
不是还有更巧妙的方法呢？ | B*****t
发帖数: 335 | 6 不解释了， 给你个code参考一下就明白了
#include
using namespace std;
int main() {
const int ANumNotInArray = 0x7fffffff;
class Node {
public:
int x, cnt;
}d[3];
int m[] = {3, 2, 6, 3, 2, 1, 6, 3, 6, 2, 7};
int n, i, j;
n = sizeof(m)/sizeof(int);
bool found = false;
for(i=0; i<3; i++) {
d[i].x = ANumNotInArray;
d[i].cnt = 0;
}
for(i=0; i
for(j=0; j<3; j++) {
if(m[i]==d[j].x) {
d[j].cnt++; f
【在 r****o 的大作中提到】
: 还是不懂。
: 能不能再详细一点 :>)
| b******v
发帖数: 1493 | 7 学习了
【在 B*****t 的大作中提到】
: 不解释了， 给你个code参考一下就明白了
: #include
: using namespace std;
: int main() {
: const int ANumNotInArray = 0x7fffffff;
: class Node {
: public:
: int x, cnt;
: }d[3];
: int m[] = {3, 2, 6, 3, 2, 1, 6, 3, 6, 2, 7};
| r****o
发帖数: 1950 | 8 非常感谢。
不过我运行了一下你的程序，发现当m[]={3,3,3,7,2,2,6,1,6,2,6}时，
程序输出6 7 2.
能否麻烦你再改改 :)
【在 B*****t 的大作中提到】
: 不解释了， 给你个code参考一下就明白了
: #include
: using namespace std;
: int main() {
: const int ANumNotInArray = 0x7fffffff;
: class Node {
: public:
: int x, cnt;
: }d[3];
: int m[] = {3, 2, 6, 3, 2, 1, 6, 3, 6, 2, 7};
| r****o
发帖数: 1950 | 9 非常感谢。
不过运行新代码后发现，
当m[]={2,1,1,3,3,3,2,6,6,6,2}时，程序输出 6 1 3.
能不能再看看哪儿不对?
【在 B*****t 的大作中提到】
: 不解释了， 给你个code参考一下就明白了
: #include
: using namespace std;
: int main() {
: const int ANumNotInArray = 0x7fffffff;
: class Node {
: public:
: int x, cnt;
: }d[3];
: int m[] = {3, 2, 6, 3, 2, 1, 6, 3, 6, 2, 7};
| B*****t
发帖数: 335 | 10 sorry，确实有问题，可能是算法本身就不对，回头再想想，头脑已经不清楚了。
【在 r****o 的大作中提到】
: 非常感谢。
: 不过运行新代码后发现，
: 当m[]={2,1,1,3,3,3,2,6,6,6,2}时，程序输出 6 1 3.
: 能不能再看看哪儿不对?
| r****o
发帖数: 1950 | 11 呵呵，多谢了。我在想，有没有比较好的不用hashtable的类似只找一个majority的数
的算法呢？
【在 B*****t 的大作中提到】
: sorry，确实有问题，可能是算法本身就不对，回头再想想，头脑已经不清楚了。
| B*****t
发帖数: 335 | 12 又改了一下，你看看还有没有bug
#include
using namespace std;
int main() {
const int ANumNotInArray = 0x7fffffff;
class Node {
public:
int x, cnt;
}d[3];
int m[] = {3,3,3,7,2,2,6,1,6,2,6};
int n, i, j, ix;
n = sizeof(m)/sizeof(int);
bool found = false;
for(i=0; i<3; i++) {
d[i].x = ANumNotInArray;
d[i].cnt = 0;
}
for(i=0; i
for(j=0; j<3; j++) {
if(m[i]==d[j].x) {
d[j].cnt++; found = true
【在 r****o 的大作中提到】
: 非常感谢。
: 不过运行新代码后发现，
: 当m[]={2,1,1,3,3,3,2,6,6,6,2}时，程序输出 6 1 3.
: 能不能再看看哪儿不对?
| r****o
发帖数: 1950 | 13 这个我没有挑出bug,
多谢了！！！
【在 B*****t 的大作中提到】
: 又改了一下，你看看还有没有bug
: #include
: using namespace std;
: int main() {
: const int ANumNotInArray = 0x7fffffff;
: class Node {
: public:
: int x, cnt;
: }d[3];
: int m[] = {3,3,3,7,2,2,6,1,6,2,6};
|
|
