O(n) for construction and O(n) memory but O(1) for pick up


  • 0
    S

    Though not pass because of memory limit exceeded...

    class Solution {
    public:
    Solution(vector<int> nums) {
    int k = 0;
    for (int i = 0; i < nums.size(); i++) {
    if (hash.find(nums[i]) == hash.end()) {
    hash[nums[i]] = k;
    vector<int> temp {i};
    s.push_back(temp);
    k++;
    }
    else {
    s[hash[nums[i]]].push_back(i);
    }
    }
    }

    int pick(int target) {
        int k = hash[target];
        int n = rand()%s[k].size();
        return s[k][n];
    }
    vector <vector<int>> s; 
    unordered_map <int ,int> hash; 
    

    };


Log in to reply
 

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