11package medium ;
22
3- public class PhoneDirectory {
3+ import java .util .HashSet ;
4+ import java .util .LinkedList ;
5+ import java .util .Queue ;
6+ import java .util .Set ;
47
8+ public class PhoneDirectory {
9+ //this runs in 669 ms, its get() method is O(n)
510boolean []availableNumbers ;
611
712/** Initialize your data structure here
@@ -36,3 +41,44 @@ public void release(int number) {
3641 }
3742
3843}
44+
45+ class PhoneDirectory_use_set {
46+ //this runs in 532 ms, its get() method is O(1)
47+
48+ Queue <Integer >phoneBooks ;
49+ Set <Integer >used ;
50+
51+ /** Initialize your data structure here
52+ @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
53+ public PhoneDirectory_use_set (int maxNumbers ) {
54+ phoneBooks =new LinkedList <Integer >();
55+ int number =0 ;
56+ while (maxNumbers -- >0 ){
57+ phoneBooks .add (number ++);
58+ }
59+ used =new HashSet <Integer >();
60+ }
61+
62+ /** Provide a number which is not assigned to anyone.
63+ @return - Return an available number. Return -1 if none is available. */
64+ public int get () {
65+ if (phoneBooks .peek () ==null )return -1 ;
66+ int number =phoneBooks .poll ();
67+ used .add (number );
68+ return number ;
69+ }
70+
71+ /** Check if a number is available or not. */
72+ public boolean check (int number ) {
73+ return !used .contains (number );
74+ }
75+
76+ /** Recycle or release a number. */
77+ public void release (int number ) {
78+ if (used .remove (number )){
79+ phoneBooks .add (number );
80+ }
81+ }
82+
83+
84+ }