Java Solution with Queue and array for efficiency, O(1)


  • 1

    Use a queue for get, O(1).
    Use another array for check, O(1)
    Only need to do one-time initialization when starting, O(N)

    Queue<Integer> availableQ;
        int[] checkList;
        public PhoneDirectory(int maxNumbers) {
            availableQ = new LinkedList<Integer>();
            checkList = new int[maxNumbers];
            for(int i=0;i<maxNumbers;i++)
                availableQ.add(i);
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            if(availableQ.isEmpty()==true) return -1;
            else checkList[availableQ.peek()] = -1;
            return availableQ.poll();
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            if(checkList[number]==-1) return false;
            else return true;
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if(checkList[number]==-1){
                checkList[number] = 0;
                availableQ.add(number);
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.