@Gene :
sorting given input will give:-
1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
consider 2-d array;
4 3 5 2 1 - frequency of corresponding unique data at position arr[1][]
1 2 3 4 5 - unique data
min-heapify arr[0][] - first row and keep track of
the corresponding frequency.
now extract-min and
Any reasonable algorithm is goingto compute a histogram of the data
then sort into frequency order to produce the output.
The histogram (map from data values to frequency counts) can be stored
in a simple array if the data are small integers as in the example.
If the data are not nice, then a
This problem is very old and O(NlgN) may be the best runtime .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@Gene:
I am wondering about the the N log N factor.
I agree with the log N component, but, can u clarify on the first component
in N * log N (N being no. of unique numbers)
we still check for each element in the input (n), the binary search among
'N' unique values.
Isn't this n log N
n -
Hashmapping O(n)
On 25-Dec-2011 2:15 AM, sravanreddy001 sravanreddy...@gmail.com wrote:
any better approach than O(N log N) time?
maintain a heap of nodes value, count
for each element, if already present increase the count. Else add the
elements.
Max-Heap -- fetch the node, print it
What about the case of the numbers having same frequency?
Which one should come first?
On Dec 24, 11:18 pm, atul anand atul.87fri...@gmail.com wrote:
first sort the given array , you will get
1,1,1,1,2,2,2,3,3,3,3,3,4,4,5
now count frequency of each number and insert it into min heap.
each
@Atul..your solution is correct and would do the job but its complexity wud
be nlogn .
Any better way of solving it ?
Regards
Ankur
On Sun, Dec 25, 2011 at 2:10 AM, sravanreddy001 sravanreddy...@gmail.comwrote:
any better approach than O(N log N) time?
maintain a heap of nodes value, count
fpr the nos with same frequency , the one having lower value shud come first
For ex
3,1,1,3,1,3,2
Here 1 should come first
so
2,1,1,1,3,3,3
On Sun, Dec 25, 2011 at 11:18 AM, top coder topcode...@gmail.com wrote:
What about the case of the numbers having same frequency?
Which one should
@ankur : if i am able to figure out a better solution , i will post.but i
guess nlogn is the best we can get.
On Sun, Dec 25, 2011 at 4:50 PM, Ankur Garg ankurga...@gmail.com wrote:
@Atul..your solution is correct and would do the job but its complexity
wud be nlogn .
Any better way of
LSD Radix sort can be used:
- First, it will sort the no. This will take O(k.n) (k: max no of digits in
a number; n: no of integers)
- Second, since the no are now sorted, scan all the integers and get their
frequency count. O(n)
- Use radix sort again to sort the frequency count in decreasing
any better approach than O(N log N) time?
maintain a heap of nodes value, count
for each element, if already present increase the count. Else add the
elements.
Max-Heap -- fetch the node, print it count number of times, (time to
search in heap -- log N)
doing this for N elements.
--
You
11 matches
Mail list logo
