C++ HashMap Meet Problem


  • 0
    B

    I want to use unordered_map to preprocess in O(N), which saves index of each number.

    e.g.: for array = {1,2,3,3,3}
    build:

    [1]->{0}
    [2]->{1}
    [3]->{2,3,4}
    

    and pick in O(1) by:

    id = rand()%the_target_list_size
    index = map[target][id]
    

    But Ran into Problems:

    Memory Limit Exceeded

    Similar Solution is here :

    https://discuss.leetcode.com/topic/58368/o-n-to-pre-process-and-o-1-to-pick

    But the author seems do not have the problem

    Here is the code:

    class Solution {
    public:
        unordered_map<int, vector<int> > indexer;
        Solution(vector<int> nums) { 
            for(int i=0;i<nums.size();i++)
               indexer[nums[i]].push_back(i);
        }
        int pick(int target) {
            int id = std::rand()%indexer[target].size();
            return indexer[target][id];
        }
    };
    

  • 0
    B

    As the problem said:

    Note:
    The array size can be very large. Solution that uses too much extra space will not pass the judge.
    

    Hashmap is not a good solution because it cost too much memory.

    The author want us use the Reservoir Sampling method to solve the problem. Which is O(N) Time Complexity.


  • -1
    A

    But the HashMap in fact takes the same memory as copy a vector.


  • 0
    B

    @aubee
    Well, HashMap takes far more memory than Vector

    In most STL version

    Vector alloc twice memory(2N) of the last state size (N) if it is over bound.

    But Hash: https://en.wikipedia.org/wiki/Hash_function
    We need a lot of ( sometimes even x times; x could be very large ) memory to ensure hash success.


Log in to reply
 

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