例题
n的范围是1e5,时间限定1s
- 如果使用vector+count(g.begin(),g.end(),x),时间复杂度应该是o(n*n)
因为vector是无序的,查找的复杂度应该是o(n)
- 如果使用set+set.count(val),复杂度o(n*logn)
因为set有序,使用二分查找
- 如果使用map+map.count(val),复杂度o(n)
因为map的查找是o(1)
回到本节一开始提到的一类问题：“查找一个元素是不是存在”。现在我们有4件工具来帮我们解决这个问题：
unordered_set O(1)
unordered_map O(1)
set O(logN)
map O(logN)