# [LeetCode] 379. Design Phone Directory 设计电话目录

2021年09月15日 阅读数：4

Design a Phone Directory which supports the following operations:html

1. `get`: Provide a number which is not assigned to anyone.
2. `check`: Check if a number is available or not.
3. `release`: Recycle or release a number.

Example:java

```// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);

// It can return any available phone number. Here we assume it returns 0.
directory.get();

// Assume it returns 1.
directory.get();

// The number 2 is available, so return true.
directory.check(2);

// It returns 2, the only number that is left.
directory.get();

// The number 2 is no longer available, so return false.
directory.check(2);

// Release number 2 back to the pool.
directory.release(2);

// Number 2 is available again, return true.
directory.check(2);```

PhoneDirectory(int maxNumbers)：时间复杂度是O(n)。
int get()：时间复杂度是O(1)。
bool check(int number)：时间复杂度是O(1)。
void release(int number)：时间复杂度是O(1)。

PhoneDirectory(int maxNumbers)：时间复杂度是O(nlogn)。
int get()：时间复杂度是O(logn)。
bool check(int number)：时间复杂度是O(logn)。
void release(int number)：时间复杂度是O(logn)。

PhoneDirectory(int maxNumbers)：时间复杂度是O(n)。
int get()：时间复杂度是O(1)。
bool check(int number)：时间复杂度是O(1)。
void release(int number)：时间复杂度是O(1)。

G家：Phone number assignment

Java:

```public class PhoneDirectory {
int max;
HashSet<Integer> set;

/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public PhoneDirectory(int maxNumbers) {
set = new HashSet<Integer>();
for(int i=0; i<maxNumbers; i++){
queue.offer(i);
}
max=maxNumbers-1;
}

/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
public int get() {
if(queue.isEmpty())
return -1;

int e = queue.poll();
return e;
}

/** Check if a number is available or not. */
public boolean check(int number) {
return !set.contains(number) && number<=max;
}

/** Recycle or release a number. */
public void release(int number) {
if(set.contains(number)){
set.remove(number);
queue.offer(number);
}
}
}　　```

Python:

```# init:     Time: O(n), Space: O(n)
# get:      Time: O(1), Space: O(1)
# check:    Time: O(1), Space: O(1)
# release:  Time: O(1), Space: O(1)
class PhoneDirectory(object):
def __init__(self, maxNumbers):
"""
@param maxNumbers - The maximum numbers that can be stored in the phone directory.
:type maxNumbers: int
"""
self.__curr = 0
self.__numbers = range(maxNumbers)
self.__used = [False] * maxNumbers

def get(self):
"""
Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available.
:rtype: int
"""
if self.__curr == len(self.__numbers):
return -1
number = self.__numbers[self.__curr]
self.__curr += 1
self.__used[number] = True
return number

def check(self, number):
"""
Check if a number is available or not.
:type number: int
:rtype: bool
"""
return 0 <= number < len(self.__numbers) and \
not self.__used[number]

def release(self, number):
"""
Recycle or release a number.
:type number: int
:rtype: void
"""
if not 0 <= number < len(self.__numbers) or \
not self.__used[number]:
return
self.__used[number] = False
self.__curr -= 1
self.__numbers[self.__curr] = number

# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)　　```

C++: Hash table

```class PhoneDirectory {
public:
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
PhoneDirectory(int maxNumbers) {
for (int i = 0; i < maxNumbers; ++i) {
hash.insert(i);
}
}

/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
if (hash.empty()) {
return -1;
}
int ret = *(hash.begin());
hash.erase(hash.begin());
return ret;
}

/** Check if a number is available or not. */
bool check(int number) {
return hash.count(number) > 0;
}

/** Recycle or release a number. */
void release(int number) {
hash.insert(number);
}
private:
unordered_set<int> hash;
};

/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj.get();
* bool param_2 = obj.check(number);
* obj.release(number);
*/
```

C++: binary tree

```class PhoneDirectory {
public:
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
PhoneDirectory(int maxNumbers) {
for (int i = 0; i < maxNumbers; ++i) {
st.insert(i);
}
}

/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
if (st.empty()) {
return -1;
}
int ret = *st.begin();
st.erase(st.begin());
return ret;
}

/** Check if a number is available or not. */
bool check(int number) {
return st.find(number) != st.end();
}

/** Recycle or release a number. */
void release(int number) {
st.insert(number);
}
private:
set<int> st;
};

/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj.get();
* bool param_2 = obj.check(number);
* obj.release(number);
*/
```

C++:　array

```class PhoneDirectory {
public:
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
PhoneDirectory(int maxNumbers) {
n = maxNumbers;
numbers.resize(n);
for(int i = 0; i < n; ++i) {
numbers[i] = i;
}
is_available.resize(n, true);
}

/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
if(n == 0) {
return -1;
}
int num = numbers[--n];
is_available[num] = false;
return num;
}

/** Check if a number is available or not. */
bool check(int number) {
return is_available[number];
}

/** Recycle or release a number. */
void release(int number) {
return;
}
numbers[n++] = number;
is_available[number] = true;
}
private:
vector<int> numbers;            // the number array
vector<bool> is_available;      // indicate whether the number is available
int n;                          // the current available numbers
};

/**
* Your PhoneDirectory object will be instantiated and called as such:
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
* int param_1 = obj.get();
* bool param_2 = obj.check(number);
* obj.release(number);
*/　　　```

C++:

```class PhoneDirectory {
public:
/** Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
PhoneDirectory(int maxNumbers) {
max_num = maxNumbers;
next = idx = 0;
recycle.resize(max_num);
flag.resize(max_num, 1);
}

/** Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available. */
int get() {
if (next == max_num && idx <= 0) return -1;
if (idx > 0) {
int t = recycle[--idx];
flag[t] = 0;
return t;
}
flag[next] = false;
return next++;
}

/** Check if a number is available or not. */
bool check(int number) {
return number >= 0 && number < max_num && flag[number];
}

/** Recycle or release a number. */
void release(int number) {
if (number >= 0 && number < max_num && !flag[number]) {
recycle[idx++] = number;
flag[number] = 1;
}
}
private:
int max_num, next, idx;
vector<int> recycle, flag;
};
```