C++ 128m Solution, Real O(1) Solution


  • 29
    C

    There are two data member in the solution

    1. a vector nums
    2. an unordered_map m

    The key of m is the val, the value of m is a vector contains indices where the val appears in nums.
    Each element of nums is a pair, the first element of the pair is val itself, the second element of the pair is an index into m[val].
    There is a relationship between nums and m:

    m[nums[i].first][nums[i].second] == i;

    class RandomizedCollection {
    public:
        /** 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) {
            auto result = m.find(val) == m.end();
            
            m[val].push_back(nums.size());
            nums.push_back(pair<int, int>(val, m[val].size() - 1));
            
            return result;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto result = m.find(val) != m.end();
            if(result)
            {
                auto last = nums.back();
                m[last.first][last.second] = m[val].back();
                nums[m[val].back()] = last;
                m[val].pop_back();
                if(m[val].empty()) m.erase(val);
                nums.pop_back();
            }
            return result;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return nums[rand() % nums.size()].first;
        }
    private:
        vector<pair<int, int>> nums;
        unordered_map<int, vector<int>> m;
    };
    

  • 1
    P

    Thanks a lot. Nice and clean solution.


  • 1
    Z

    Really smart solution! Thank you a lot!


  • 0

    Best solution in C++ so far. Really brilliant!


  • 2
    L

    Brilliant solution. Here is my Java version according to this answer.

    public class RandomizedCollection {
        private Map<Integer, List<Integer>> map;
        private List<int[]> nums;
        private Random rnd;
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            map = new HashMap<>();
            nums = new ArrayList<>();
            rnd = 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) {
            boolean res = !map.containsKey(val);
            if(res) map.put(val, new ArrayList<>());
            map.get(val).add(nums.size());
            nums.add(new int[]{val, map.get(val).size() - 1});
            return res;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            boolean res = map.containsKey(val);
            if(res) {
                List<Integer> valList = map.get(val);
                int valLastIndex = valList.get(valList.size() - 1);
                
                int[] swapNum = nums.get(nums.size() - 1);
                int swapVal = swapNum[0], swapIndex = swapNum[1];
                
                map.get(swapVal).set(swapIndex, valLastIndex);
                nums.set(valLastIndex, swapNum);
                
                if(valList.size() == 1) map.remove(val);
                else valList.remove(valList.size() - 1);
                
                nums.remove(nums.size() - 1);
            }
            return res;
        }
        
        /** Get a random element from the collection. */
        public int getRandom() {
            return nums.get(rnd.nextInt(nums.size()))[0];
        }
    }
    
    

  • 0
    O

    I used a set to store val's positions in nums, 63ms

    class RandomizedCollection {
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            srand(time(0));
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            bool has_key = pos_map.find(val) != pos_map.end();
            pos_map[val].insert(nums.size());
            nums.push_back(val);
            return !has_key;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (pos_map.find(val) == pos_map.end())
                return false;
            
            int pos_rm = *(pos_map[val].begin());
            pos_map[val].erase(pos_rm);
            if (pos_map[val].empty())
                pos_map.erase(val);
            
            if (pos_rm != nums.size() - 1) {
                int pos_mv = nums.size() - 1, val_mv = nums.back();
                nums[pos_rm] = val_mv;
                pos_map[val_mv].erase(pos_mv);
                pos_map[val_mv].insert(pos_rm);
            }
            nums.pop_back();
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return nums[rand() % nums.size()];
        }
        
    private:
        vector<int> nums;
        unordered_map<int, unordered_set<int>> pos_map;
    };
    

  • 0
    O
    This post is deleted!

  • 0
    M

    i dont think the getRandom() can make sure the probability of each element being returned is linearly related to the number of same value the collection contains.


Log in to reply
 

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