Java LinkedHashSet solution O(1) for get(), check(), and release(); O(n) construction.


  • 0
    public class PhoneDirectory {
    
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        LinkedHashSet<Integer> nums = new LinkedHashSet<>();
        int max;
        public PhoneDirectory(int maxNumbers) {
            max = maxNumbers;
            for (int i=0; i<max; i++){
                nums.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 (nums.isEmpty()) return -1;
            int ret = nums.iterator().next();
            nums.remove(ret);
            return ret;
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            return nums.contains(number);
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if (number < max && ! check(number) ){
                nums.add(number);
            }
        }
    }
    

  • 0

    How about making the constructor O(1) as well?


  • 0

    @StefanPochmann
    Yes, I had another solution here, which has O(1) for each operation.


Log in to reply
 

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