Custom DS Design

经典题目

380 Insert Delete GetRandom O(1)

• Follow up, what if duplicates are allowed. LC 381

380 Sol

// HashMap + ArrayList
// 有个 corner case 需要 handle，就是调用 remove 操作时，
// list 中 只有一个元素 和 有多个元素 的情况，需要区分开来。

class RandomizedSet {
    Map<Integer, Integer> map;
    List<Integer> list;
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<Integer, Integer>();
        list = new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            map.put(val, list.size());
            list.add(val);
            return true;
        }
        return false;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (map.containsKey(val)) {
            int index = map.get(val);
            // put the last element in the list to index
            if (index == list.size() - 1) {
                list.remove(list.size() - 1);
                map.remove(val);
            } else {
                int tailValue = list.get(list.size() - 1);
                list.set(index, tailValue);
                // remove the last element
                list.remove(list.size() - 1);
                map.remove(val);
                map.put(tailValue, index);
            }
            return true;
        }
        return false;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random random = new Random();
        return list.get(random.nextInt(list.size()));
    }
}

381 Follow up --- Duplicates Allowed

// Follow up 多了 duplicates
// 因为所有操作需要做到 O(1)，并且 getRandom() 跟比重有关
// 所以这里需要一个 Map<Integer, Set<Integer>> ，记录不同值的所有index
// Remove() 的策略还是跟之前一样，取一个index，然后和list 最后一个index交换
// 注意，交换之后，必须确保所有变量的物理意义不变。
class RandomizedCollection {
    List<Integer> list;
    // key : unique value
    // value: list of indexes respectively
    Map<Integer, Set<Integer>> map;
    Random rd;
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rd = new Random();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        list.add(val);
        if (map.containsKey(val)) {
            map.get(val).add(list.size() - 1);
            return false;
        } else {
            Set<Integer> indexes = new HashSet<>();
            indexes.add(list.size() - 1);
            map.put(val, indexes);
            return true;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (map.containsKey(val)) {
            Set<Integer> indexes = map.get(val);
            Iterator<Integer> itr = indexes.iterator();
            if (itr.hasNext()) {
                int valIndex = itr.next();              
                // Condition 1: valIndex is the last index of list
                // Then, we just need to remove it from list and map.
                if (valIndex == list.size() - 1) {
                    indexes.remove(valIndex);
                    list.remove(list.size() - 1);
                } else {
                    // Condition 2: valIndex is not the last index of list
                    // Then, swap it with the last element of list.
                    // Remove the index record in map
                    // Update the index records of swapped element in map
                    // Remove the last element of list
                                        
                    // remove index
                    indexes.remove(valIndex);                  
                    int tailVal = list.get(list.size() - 1);
                    Set<Integer> tailIndexes = map.get(tailVal);
                    // swap valIndex and last element
                    list.set(valIndex, tailVal);
                    // delete the last element in list
                    list.remove(list.size() - 1);
                    // update index
                    tailIndexes.remove(list.size());
                    tailIndexes.add(valIndex);
                }
                return true;
            } else {
                map.remove(val);
                return false;
            }
        } 
        return false;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        int index = rd.nextInt(list.size());
        return list.get(index);
    }
}

895. Maximum Frequency Stack

class FreqStack {
	/*
		Method 1: HashMap of Stack.
		
		levelMap: {frequency: stack of numbers}
		freqMap: {number: frequency}
		
		For example:
		5 -> 1 -> 5 -> 2 -> 5 -> 1 -> 4
		
		levelMap: {
			1 : {5, 1, 2, 4}
			2 : {5, 1}
			3 : {5}
		}
		freqMap: {
			1:2
			2:1
			4:1
			5:3
		}
	*/
	
    private int maxFreq = 0;
    private Map<Integer, Deque<Integer>> levelMap; 
    private Map<Integer, Integer> freqMap;
    
    public FreqStack() {
        freqMap = new HashMap<>();
        levelMap = new HashMap<>();
    }
    
    public void push(int x) {
        int newFreq = freqMap.getOrDefault(x, 0) + 1;
        freqMap.put(x, newFreq);
        maxFreq = Math.max(maxFreq, newFreq);
        
        Deque<Integer> stack = levelMap.get(newFreq);
        if (stack == null) {
            stack = new LinkedList<>();
        }
        stack.offerLast(x);
        levelMap.put(newFreq, stack);
    }
    
    public int pop() {
        int res = levelMap.get(maxFreq).pollLast();
        freqMap.put(res, maxFreq - 1);
        if (levelMap.get(maxFreq).size() == 0) {
            maxFreq -= 1;
        }
        return res;
    }
}