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

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;
    }
}