Java开发网 - 怎樣找n個數中,眾數?

Topic: 怎樣找n個數中,眾數?

1.怎樣找n個數中,眾數?	Copy to clipboard
Posted by: angus203 Posted on: 2005-11-18 19:28 怎樣找 n 個數中,眾數(出現次數最多)?

2.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: anatoranato Posted on: 2005-11-19 06:23 这样做吧:一个一个地数,并记录下每一个数的个数,当某个数出现的次数比剩下的数的总数还大时,这个数就是众数. 还有更快的算法吗?

3.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: ranchgirl Posted on: 2005-11-19 08:30 anatoranato wrote: 这样做吧:一个一个地数,并记录下每一个数的个数,当某个数出现的次数比剩下的数的总数还大时,这个数就是众数. 还有更快的算法吗? Obviously wrong algorithm! A simple counter example 3,3,3,5,5,5,5,3,3

4.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: angus203 Posted on: 2005-11-19 09:11 那麼應該怎樣做?

5.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: anatoranato Posted on: 2005-11-19 22:32 不好意思,说错了,改为: 一个一个地数,并记录下每一个数的个数,当当前出现次数最多的数所出现次数,与当前出现次数第二多的数的次数的差比剩下的数的总数还大时,这个数就是众数.还有更快的算法吗?

6.Re:怎樣找n個數中,眾數? [Re: angus203]

Copy to clipboard

Posted by: ranchgirl
Posted on: 2005-11-20 00:41

anatoranato wrote:
一个一个地数,并记录下每一个数的个数,当当前出现次数最多的数所出现次数,与当前出现次数第二多的数的次数的差比剩下的数的总数还大时,这个数就是众数.还有更快的算法吗?

"还有更快的算法吗?"

Your algorithm is very bad, and very slow! You way too much increase number of comparisons and calculations. The less comparison, the faster!

You do 3 comparison for each number count
1) compare to current maximum count
2) compare or calculate to the second maximum
3) compare to the number left

It is much better just count all of them. There is no comparison at all in the process.

Then you get the maximum out by comparison of the counting result.
1) The worst case is n-1 comparisons, if all numbers are different.
2) The best case is no comparison, if all numbers are the same.
3) The most possible case is m comparisons, m << n-1.

Attention: This comparison count I am talking about does not include the data structure you choose to use to store the number and its count etc.

Choose an efficient data structure to store the number and its count. I think TreeMap might be a good choice.

I can see you are very interested on algoritnm, that is very good.
However, you need to read a book, and practice a little more.
Right now, you'd better not to give others' many wrong instructions.

Thanks!

7.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: zoudejian123 Posted on: 2005-11-20 11:49 应该怎么实现呢？

8.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: zoudejian123 Posted on: 2005-11-20 11:51 应该怎么实现呢？

9.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: ranchgirl Posted on: 2005-11-20 13:07 I have told you the algorithm. You need to write your own code!!!!

10.Re:怎樣找n個數中,眾數? [Re: angus203]

Copy to clipboard

Posted by: anatoranato
Posted on: 2005-11-20 22:12

叫gongshi的外国朋友,我不得不承认,你的英语真的不错,不过在这个求众数的问题上,我觉得你有点过于武断了.你给出的所谓的算法就是这两句:t is much better just count all of them.Then you get the maximum out by comparison of the counting result.
问题就出在"just count all of them".怎样把它们全数一遍呢?当你面对整数序列中的一个新数时,你怎么知道它是否出现过,出现过多少次?是不是要做一个数据结构来计数每个出现过的整数的出现的次数?那么你就得去和出现过的数去比较才能找到它并确定它,这里不也是有比较吗?其实我所给出的算法只是在你所给的算法上加了一个加速得出结果的条件而已,如果你要找的众数它出现的次数最终与次众数出现的次数大体相当,那么我的算法显然没有你的高,但是如果你要找的出众的那个数真的很出众,我想,还是我的快一些吧.

11.Re:怎樣找n個數中,眾數? [Re: angus203]

Copy to clipboard

Posted by: ranchgirl
Posted on: 2005-11-21 00:26

Haha, whatever!

If you believer your algorithm has some chance to be faster than mine, then just go a head to believe it....

BTW, did you read my algorithm analysis and bolded part started with Attention: ... carefully??? Wink

Actually, "如果你要找的出众的那个数真的很出众", my algorithm is much faster than the average case... Smile

12.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: phoenix451 Posted on: 2005-11-21 09:41 gongshi ,你好，我觉得你的算法是在n个数字中找最大的嗉子的算法，，我们题目是找出现次数最多的，既然是最多的，我觉得，你不数完了怎么知道呢？

13.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: phoenix451 Posted on: 2005-11-21 09:44 呵呵，错了，不是“嗉子”，是“数字”，sorry

14.Re:怎樣找n個數中,眾數? [Re: angus203]

Copy to clipboard

Posted by: ranchgirl
Posted on: 2005-11-21 10:22

phoenix451 wrote:
我们题目是找出现次数最多的，既然是最多的，我觉得，你不数完了怎么知道呢？

When did I say "不数完了", I said count all of them.
You did not understand what I was talking about.

My Algorithm:
1) I use TreeMap to insert different numbers (key) with its count (value) using map.put(key, value) method. Since map only allow inserting the same key once, if it is there already, increase the value count.
2) Use wrapper class Integer for number (key) and count (value)
3) Finish all numbers and their value (count)
4) Get the entrySet of the map, found the maximum value (count), the key (number) of that map.entry will be your mode (眾數).
5) Done!!!!

I have coded the algorithm, and it works with any n, for example n = 100,000,000. I used random number generator to generate the numbers, since number can repeat, the TreeMap is not too big, which depends how you allow the range of the random number generator.

The code finds out the mode (眾數) correctly without any problem!

You don't have to use my algorithm, whatever you like, as long as it works!

I will shut my mouth up from this thread, no matter what question or critics comes here.

Don't ask for my code (only 67 lines include spaces for readability). Sorry! I will not publish it, period!

Thanks!

15.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: anatoranato Posted on: 2005-11-21 21:55 1 , 2, 2, 2, 3.数到第三个2的时候不就知道,2肯定是最多了吗?所以不是总是需要数完的

16.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: anatoranato Posted on: 2005-11-21 22:03 不如我们各用程序把各人的想法实现,再产后随机数数列,测它一千一万回,看看怎么样?小弟我也准备面对结果了.如何?

17.Re:怎樣找n個數中,眾數? [Re: anatoranato]

Copy to clipboard

Posted by: angus203
Posted on: 2005-11-22 20:18

anatoranato wrote:
不好意思,说错了,改为: 一个一个地数,并记录下每一个数的个数,当当前出现次数最多的数所出现次数,与当前出现次数第二多的数的次数的差比剩下的数的总数还大时,这个数就是众数.还有更快的算法吗?

現在不就是找出現次數最多的數~~
為什麼找完最多,還要找第二多 ??
不明白~
可否寫一個 example

18.Re:怎樣找n個數中,眾數? [Re: gongshi]

Copy to clipboard

Posted by: angus203
Posted on: 2005-11-23 19:37

You do 3 comparison for each number count
1) compare to current maximum count
2) compare or calculate to the second maximum
3) compare to the number left

Then you get the maximum out by comparison of the counting result.
1) The worst case is n-1 comparisons, if all numbers are different.
2) The best case is no comparison, if all numbers are the same.
3) The most possible case is m comparisons, m << n-1.

找完最大數字和第二大數字後
怎樣去比較??
不太明白

19.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: anatoranato Posted on: 2005-11-24 21:51 这几天加班忙,只有周末来写了.

20.Re:怎樣找n個數中,眾數? [Re: angus203]	Copy to clipboard
Posted by: ranchgirl Posted on: 2005-11-25 12:15 anatoranato wrote: 这几天加班忙,只有周末来写了. To anatoranato Please do NOT do other's homework for him/her. Thanks! By the way, I sent a PM (悄悄话) to you on 11-21-2005, you don't read at all? Read, please! Thanks!