@ross: It seems that after discretization , the time complexity still would be O(nlogn).
The discretization idea is: say there are 4 numbers, each of them is in the range[1, 16]. e.g. 12 3 12 15 You can do one time transverse to map each of them to a global increasing index (hashing is the appropriate method) 12 ---> 1 3 ---> 2 15 ---> 3 but we still need some data structure to hold the order of the numbers which is still O(nlogn). for this idea, using STL map<Tkey, TValue> would be much easier... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
