Smilence.yu
BAN USERAs it is only required to find the latest version, you don't need to actually sort all of them.
First, convert the strings to vectors; e.g "3.12.4.7" to {3,12,4,7}( I use a string stream )
Then you have two options:
1.From left to right, for each token, find the max token, and erase all the vectors missing that token or less than the max token. Finally you will get only one vector.( Of course you can use a bool array instead of actually remove vectors)
2.Implement a compare functions for two vectors. Compare the first element till the last and return which vector is prior. Use this to traverse all the vectors to find the "max" vector.
Both require about O(k * n) time. K is the max length of the vector.
As it is only required to find the latest version, you don't need to actually sort all of them.
First, convert the strings to vectors; e.g "3.12.4.7" to {3,12,4,7}( I use a string stream )
Then you have two options:
1.From left to right, for each token, find the max token, and erase all the vectors missing that token or less than the max token. Finally you will get only one vector.( Of course you can use a bool array instead of actually remove vectors)
2.Implement a compare functions for two vectors. Compare the first element till the last and return which vector is prior. Use this to traverse all the vectors to find the "max" vector.
Both require about O(k * n) time. K is the max length of the vector.
The most optimized code I can think of.
The key point is establish a list of primes and fill it until the size increase to n.
And I add 2 to num at a time as odd numbers can't be prime numbers.
- Smilence.yu October 05, 2013