How to check if an integer is in a set of given ranges? [closed]

by

The time efficient way to do this is to create a Bitset with a bit set for all of the integers in all of the sets. Then you can test for membership with a single O(1) call.

The problem is that if the combined range of the integers is large, then the Bitset will take a lot of memory.

A second approach is to combine overlapping ranges, and construct a TreeMap<Integer, Integer> where the key is the lower bound and value is the upper bound of each combined range. Then use TreeMap::floorKey and a test to find the matching ranges. This procedure is O(logN) where N is the number of combined ranges. Space usage will be O(N).

More Related Contents:

  1. Data Structure in Java
  2. Deciding a Big-O notation for an algorithm
  3. HashMap get/put complexity
  4. How to convert List to Map?
  5. Which Java Collection should I use?
  6. How to detect a loop in a linked list?
  7. Stack with find-min/find-max more efficient than O(n)?
  8. Best way to create a hashmap of arraylist
  9. Anagram algorithm in java
  10. Sample Directed Graph and Topological Sort Code [closed]
  11. How to restore the PriorityQueue to its initial state before the method call?
  12. How to determine if binary tree is balanced?
  13. Hash : How does it work internally?
  14. How to implement a Median-heap
  15. The simplest algorithm for poker hand evaluation
  16. Finding the shortest path nodes with breadth first search
  17. Iterate through a HashMap [duplicate]
  18. How to sort Map values by key in Java?
  19. Good Java graph algorithm library? [closed]
  20. What is the difference between the HashMap and Map objects in Java?
  21. Understanding the workings of equals and hashCode in a HashMap
  22. Reversing a linked list in Java, recursively
  23. creating Hashmap from a JSON String
  24. Using an instance of an object as a key in hashmap, and then access it with exactly new object? [duplicate]
  25. ConcurrentHashMap and Hashtable in Java [duplicate]
  26. Limiting the max size of a HashMap in Java
  27. Java – Sort one array based on values of another array?
  28. How does ConcurrentHashMap work internally?
  29. What is the algorithm for finding the center of a circle from three points?
  30. How to convert a string to a HashMap? [duplicate]

Leave a Comment