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


  • 26
    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!


  • 1
    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!

Log in to reply
 

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