Thursday, December 19, 2013

Next Permutation

The logic is not very hard. However it is easy to make mistake at several places.

General example: 1 3 5 4 2
Step1: scan from right to left, locate the first decreasing number. 1 3 5 4 2
Step2: swap it with the smallest-larger-number (3 5 4 2) on the right.  4 5 3 2
Step3: reverse all the numbers on the right. 4 2 3 5


Need to pay attention to two test cases:
1) repeated value: 5 1 1   
2) reverse order: 5 4 3 2 1



No comments:

Post a Comment