C++ HashMap Meet Problem

  • 0

    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}


    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 :


    But the author seems do not have the problem

    Here is the code:

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

  • 0

    As the problem said:

    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

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

  • 0

    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.