algorithm - Top n elements in queue -
i have implemented queue using 2 stacks , want find top n percent elements in queue.
for example:
queue takes element in order {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
top 10% elements means 10% of 20 = 2
hence answer should 19 , 20
there 2 ways can think of
- sort queue, claculate number of items (x) n% , grab top x elements.
- selection algorithm. (i came across algorithm , based on idea of quicksort. have copy entire queue array , apply algorithm)
is there better way solve this?
a queue isn't best data structure that, should not access elements inside (most of queue implementations don't provide access operator) shouldn't sort it. so, if don't need queue due other requirements, suggest use plain array.
sorting time consuming process. read/insert queue elements can compute sum. based on known sum, number of elements , percent required, can compute threshold. then, need iterate through elements (if using queue, can extract them 1 one) , display greater computed threshold.
Comments
Post a Comment