leetcode 381. Insert Delete GetRandom O(1) - Duplicates allowed

深藏阁楼爱情的钟 2022-06-07 02:50 127阅读 0赞

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.  
insert(val): Inserts an item val to the collection.  
remove(val): Removes an item val from the collection if present.  
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.  
Example:

// Init an empty collection.  
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.  
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains \[1,1\].  
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains \[1,1,2\].  
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.  
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains \[1,2\].  
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.  
collection.getRandom();

网上看到的答案，这里就直接看代码吧，不喜欢这样类型的题。

代码如下：

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Random;
    import java.util.TreeSet;
    
    
    /*
     *  http://bookshadow.com/weblog/2016/08/09/leetcode-insert-delete-getrandom-o1-duplicates-allowed/
     */
    public class RandomizedCollection {
        
    
        private HashMap<Integer, TreeSet<Integer>> dataMap;
        private ArrayList<Integer> dataList;
         /** Initialize your data structure here. */
        public RandomizedCollection() {
            dataMap = new HashMap<Integer, TreeSet<Integer>>();
            dataList = new ArrayList<Integer>();
        }
    
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            TreeSet<Integer> idxSet = dataMap.get(val);
            if (idxSet == null) {
                idxSet = new TreeSet<Integer>();
                dataMap.put(val, idxSet);
            }
            idxSet.add(dataList.size());
            dataList.add(val);
            return idxSet.size() == 1;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            TreeSet<Integer> idxSet = dataMap.get(val);
            if (idxSet == null || idxSet.isEmpty()) {
                return false;
            }
            int idx = idxSet.pollLast(); //Last index of val
            int tail = dataList.get(dataList.size() - 1); //Tail of list
            TreeSet<Integer> tailIdxSet = dataMap.get(tail);
            if (tail != val) {
                tailIdxSet.pollLast(); //Remove last idx of list tail
                tailIdxSet.add(idx); //Add idx to tail idx set
                dataList.set(idx, tail);
            }
            dataList.remove(dataList.size() - 1);
            return true;
        }
    
        /** Get a random element from the collection. */
        public int getRandom() {
            return dataList.get(new Random().nextInt(dataList.size()));
        }
    }
    
    /**
     * Your RandomizedCollection object will be instantiated and called as such:
     * RandomizedCollection obj = new RandomizedCollection();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */

下面是C++的做法

这题是之前那道[leetcode 380. Insert Delete GetRandom O(1)][leetcode 380. Insert Delete GetRandom O_1]的拓展，与其不同的是，之前那道题不能有重复数字，而这道题可以有，那么就不能像之前那道题那样建立每个数字和其坐标的映射了，但是我们可以建立数字和其所有出现位置的集合之间的映射，虽然写法略有不同，但是思路和之前那题完全一样，都是将数组最后一个位置的元素和要删除的元素交换位置，然后删掉最后一个位置上的元素。对于insert函数，我们将要插入的数字在nums中的位置加入m\[val\]数组的末尾，然后在数组nums末尾加入val，我们判断是否有重复只要看m\[val\]数组只有刚加的val一个值还是有多个值。remove函数是这题的难点，我们首先看哈希表中有没有val，没有的话直接返回false。然后我们取出nums的尾元素，把尾元素哈希表中的位置数组中的最后一个位置更新为m\[val\]的尾元素，这样我们就可以删掉m\[val\]的尾元素了，如果m\[val\]只有一个元素，那么我们把这个映射直接删除。然后我们将nums数组中的尾元素删除，并把尾元素赋给val所在的位置，注意我们在建立哈希表的映射的时候需要用堆而不是普通的vector数组，因为我们每次remove操作后都会移除nums数组的尾元素，如果我们用vector来保存数字的坐标，而且只移出末尾数字的话，有可能出现前面的坐标大小超过了此时nums的大小的情况，就会出错，所以我们用优先队列对所有的相同数字的坐标进行自动排序，每次把最大位置的坐标移出即可，参见代码如下：

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class RandomizedCollection 
    {
    public:
        vector<int> nums;
        unordered_map<int, priority_queue<int>> m;
    
        /** Initialize your data structure here. */
        RandomizedCollection() 
        {
    
        }
    
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) 
        {
            m[val].push(nums.size());
            nums.push_back(val);
            return m[val].size() == 1;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) 
        {
            if (m[val].empty()) 
                return false;
    
            int idx = m[val].top();
            m[val].pop();
            if (nums.size() - 1 != idx)
            {
                int t = nums.back();
                nums[idx] = t;
                m[t].pop();
                m[t].push(idx);
            }
            nums.pop_back();
            return true;
        }
    
        /** Get a random element from the collection. */
        int getRandom()
        {
            return nums[rand() % nums.size()];
        }
    
    };

[leetcode 380. Insert Delete GetRandom O_1]: http://blog.csdn.net/jackzhang_123/article/details/78174246