hi, Have a problem where i want to write a program to find the ith order statistic of a data set consisting of character and their occurences. For example i have a data set consiting of B,A,C,A,B,C,A,D; here i have A with 3 occurences,B with 2 occurences C with 2 occurences and D with on occurrence. So they can be group in pairs (charaters,Number of occurences); so here we have (A,3),(B,2),(C,2) and (D,1). Assuming than k is the number of these pairs, how can i find the ith of the data set in O(k) where k is the number of pairs. Well i thought i could sort the element based their number of occurence and find their ith smallest elements but i am not sure that can work.

any help?