Design Phone Directory

Design a Phone Directory which supports the following operations:

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:

   // 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);

Tips:

1.在get()是O(n)，check O(1) release O(1)的方法里没有什么破绽

2.在全是是O(1)的方法里

For method check, what if the number passed in is larger than or equal to the maxNumbers

In that case, release function works properly, but check function does not. Boundary check is needed in release function.

Code：

复杂度高：

public class PhoneDirectory {

    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        boolean[] bitSet;
        int smallestFreeIndex;
    public PhoneDirectory(int maxNumbers) {
        this.bitSet = new boolean[maxNumbers];
    }

    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        if (smallestFreeIndex == bitSet.length) {
            return -1;
        }
        int num = smallestFreeIndex;
        bitSet[num] = true;
        for (int i = smallestFreeIndex + 1; i < bitSet.length; i++) {
            if (!bitSet[i]) {
                smallestFreeIndex = i;
                break;
            }
        }
        if (num == smallestFreeIndex) {
            smallestFreeIndex = bitSet.length;
        }
        return num;
    }

    /** Check if a number is available or not. */
    public boolean check(int number) {
        return !bitSet[number];
    }

    /** Recycle or release a number. */
    public void release(int number) {
        if (bitSet[number] = false) {
            return;
        }
        bitSet[number] = false;
        if (number < smallestFreeIndex) {
            smallestFreeIndex = number;
        }
    }
}

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

复杂度低：

Set<Integer> used = new HashSet<Integer>();
Queue<Integer> available = new LinkedList<Integer>();
int max;
public PhoneDirectory(int maxNumbers) {
    max = maxNumbers;
    for (int i = 0; i < maxNumbers; i++) {
        available.offer(i);
    }
}

public int get() {
    Integer ret = available.poll();
    if (ret == null) {
        return -1;
    }
    used.add(ret);
    return ret;
}

public boolean check(int number) {
    if (number >= max || number < 0) {
        return false;
    }
    return !used.contains(number);
}

public void release(int number) {
    if (used.remove(number)) {
        available.offer(number);
    }
}