由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 一个N个数的int数组如何找到3个majority的数?
相关主题
C++ Q96: function inheritance请教一个写程序的问题
请教C/C++小1 11 21 1211 sequence的代码
google youtube interview, 莫名被拒。。。。。。一道google电面题,估计挂了。。。
弱弱的问问 2sum, 3sum 的问题C++ Q21: size of virtual table
那道经典的求和问题C++ Q22: ostream
A家一道题C++ Q60 calling virtual function in constructor (JPMorgan)
菜鸟向大家请教个面试题C++问题
C: what is the output?弱问一个c++编程题
相关话题的讨论汇总
话题: int话题: cnt话题: anumnotinarray话题: 个数话题: sizeof
1 (共1页)
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};

1 (共1页)
相关主题
弱问一个c++编程题那道经典的求和问题
c++需要用hashtable怎么办?A家一道题
c++ class definition菜鸟向大家请教个面试题
为什么我在array里用IsOdd 总出错?C: what is the output?
C++ Q96: function inheritance请教一个写程序的问题
请教C/C++小1 11 21 1211 sequence的代码
google youtube interview, 莫名被拒。。。。。。一道google电面题,估计挂了。。。
弱弱的问问 2sum, 3sum 的问题C++ Q21: size of virtual table
相关话题的讨论汇总
话题: int话题: cnt话题: anumnotinarray话题: 个数话题: sizeof