The complexity of your code in 2.3-7 is not right!!!

[Xie-Minghui]

I think the complexity of your code in 2.3-7 whose complexity you say is O(n), is actually O(nlogn), because the complexity of inserting a element into map is log(n). You forget the cost of map.