@haruhiku Well, Since you use push_back function of vector, the time complexity will not be O(1) because the space of vector will be resized when it is used up, which is O(n) time complexity.
@yular Yes, you are right. But I think this is similar to the hashmap issue, the problem should be talking about amortized complexity. Any better ideas of a true O(1) solution?
@haruhiku We could use another hashmap instead of the vector and treat it just like a vector (i.e., with keys 0, 1, 2, 3, etc). Would be silly, as the hashmap does the same thing, but at least we'd only be lying about one thing instead of two :-P
@StefanPochmann Haha, sure. But how will you implement the getRandom()? I think using unordered_map's iterator may not fit the randomness requirement...
@haruhiku Like I said - just treat the hashmap like you treat your vector now. Your
getRandom would stay exactly like it is. Has nothing to do with iteration.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.