You are given an (unsorted) set of n integers. Given some k (1 < k <=
n), you are required to find and return the element of the set that
has more than n/k occurrences. Return None otherwise.
Required (best known) time complexity: O(n log k)
I thought of something... Lets scan each element one by one. I also
maintain a vector of sets. Initially the vector contain one empty set.
Now, as I go through the given elements, I try to insert the element
in the sets in the vector. If the element is not inserted (in case the
set already has a element of that value), i make a new set of that
element and insert it in the vector. At the end, I can see all the
elements in the set number n/k and above and we can get the result. I
think it runs in nlogK cause inserting a element in a set is logK time
(assuming a element on an average comes K times in the set).
For e.g.
say the set is 1,2,3,1,1,5,2,2
i start with a vector < {} > hving one empty set.
so it goes like <{1}>
<{1,2}>
<{1,2,3}>
<{1,2,3},{1}> ....... since new 1 is not inserted in the 1st set
<{1,2,3},{1},{1}>
<{1,2,3,5},{1},{1}>
<{1,2,3,5},{1,5},{1}>
<{1,2,3,5},{1,5,2},{1}>
<{1,2,3,5},{1,5,2},{1,2}>
Hence all elements with occurrence 3 times or more are 1 and 2 ,...as
they belng to third set.
give ur comments
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
