I wish to find the element occurring maximum number of times in a large array in linear time. I was going through the moores voting algorithm page. http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html. I think the the algorithm suggested by moore will gives incorrect results, Say if the array is AAACCBCCCCBDAEFF. It will give F as element occurin max times inthe array. plz point where I am going wrong and plz suggest some linear time algorithm without the use of hash map.
问问题
218 次
1 回答
1
Suppose you have abcdefghijklmnopqrstuvwxyzf.
To determine f as the majority element, you had to have kept it in memory, but until you reached the second f, you didn't have any special reason to do so. So that means that if you kept the first f in memory, you also kept the other letters (the 26 of them) and basically it amounts to using a hash.
I don't think it's possible to do what you want.
于 2013-09-21T03:09:31.680 回答