-
June 16th, 2010, 04:40 PM
#1
The most frequent element in a list (the mode)
I'd be thankful if someone enlighten me how to solve this problem in most efficient manner both in terms of speed and memory consumption.
Example: [4,5,6,7,12,6,8,9,4,6,8,4,97,4] the answer is 4, the only solution that occured to me is to hold counters in a hash table and pick the maximum element. However, there could some circumstances where this could be inefficient, so I wonder if some straightforward method is available.
Thanks beforehand and regards.
Last edited by AvDav; June 16th, 2010 at 04:42 PM.
-
June 18th, 2010, 03:48 PM
#2
Re: The most frequent element in a list (the mode)
The cases when your proposed solution becomes inefficient is when the hash table performance degrades to O(n^2). So, you can design the hash function(s) to avoid this, or you could use a balanced binary tree instead of a hash table, thus accepting slightly slower average case performance as a trade off for better worse case performance.
Alternatively, you could sort the list, and then go through the elements in a single pass to count them. This will result in performance similiar to the use of a balanced binary tree.
-
June 18th, 2010, 07:42 PM
#3
Re: The most frequent element in a list (the mode)
Originally Posted by laserlight
Alternatively, you could sort the list, and then go through the elements in a single pass to count them. This will result in performance similiar to the use of a balanced binary tree.
Thanks, I nearly got the idea, however am not sure how to identify the most lengthy subsequence in a sorted list in order to outline the element, could you please explain in detail?
-
June 19th, 2010, 12:49 AM
#4
Re: The most frequent element in a list (the mode)
Originally Posted by AvDav
Thanks, I nearly got the idea, however am not sure how to identify the most lengthy subsequence in a sorted list in order to outline the element, could you please explain in detail?
In a sorted list equal elements are grouped next to each other. You search the list once sequencially looking for the largest group of equal elements.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|