I need to use a data structure that can hold a set of integer. However, I need to accomplish add, return frequency of integers, search and return number of integers larger than the integer y (a parameter of the method) with the constraint that every method have to be in O(log n) time.

I plan on using Binary Search Tree so that I can easily do a search in O(log n). However, I do not know how to hold a set of integer (e.g. a list of same integers) in a BST. Can someone give some insight about the data structure to use to accomplish my big-O constraint.

share|improve this question
  • You might find this related question useful: stackoverflow.com/questions/42615150/…– William BurnhamFeb 14 at 21:11
  • A set of integers, by definition, doesn't contain the same integer multiple times. It's unclear what you are asking. My guess is that you are looking for a multiset, which can be represented in Java by a Map<E, Integer>, where E is the type of elements (in your case integers), and the associated Integer value is the number of occurences of that element.– NelfealFeb 14 at 21:19
  • Perhaps an illustration of the problem would help? Give us a collection of integers and some idea of what you'd want for outputs in certain situations.– PruneFeb 14 at 21:28
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. on topic and how to ask apply here.– PruneFeb 14 at 21:28
  • A skip list will do all these things in O(log n).– Jim MischelFeb 15 at 16:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.