379. Design Phone Directory

• Time: $O(1)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class PhoneDirectory { public: /** Initialize your data structure here @param maxNumbers - The maximum numbers that can be stored in the phone directory. */ PhoneDirectory(int maxNumbers) : next(maxNumbers) { for (int i = 0; i < maxNumbers - 1; ++i) next[i] = i + 1; next.back() = 0; } /** Provide a number which is not assigned to anyone. @return - Return an available number. Return -1 if none is available. */ int get() { if (next[number] == -1) return -1; const int ans = number; number = next[number]; next[ans] = -1; // mark as used return ans; } /** Check if a number is available or not. */ bool check(int number) { return next[number] != -1; } /** Recycle or release a number. */ void release(int number) { if (next[number] != -1) return; next[number] = this->number; this->number = number; } private: int number = 0; // current possible available number vector next; // next available number }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 class PhoneDirectory { /** * Initialize your data structure here * * @param maxNumbers - The maximum numbers that can be stored in the phone * directory. */ public PhoneDirectory(int maxNumbers) { next = new int[maxNumbers]; for (int i = 0; i < maxNumbers - 1; ++i) next[i] = i + 1; next[maxNumbers - 1] = 0; } /** * Provide a number which is not assigned to anyone. * * @return - Return an available number. Return -1 if none is available. */ public int get() { if (next[number] == -1) return -1; final int availableNum = number; number = next[number]; next[availableNum] = -1; // mark as used return ans; } /** Check if a number is available or not. */ public boolean check(int number) { return next[number] != -1; } /** Recycle or release a number. */ public void release(int number) { if (next[number] != -1) return; next[number] = this.number; this.number = number; } private int number; // current possible available number private int[] next; // next available number }