1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 19, 2014
4+ Problem: Next Permutation
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/next-permutation/
7+ Notes:
8+ Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
9+ If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
10+ The replacement must be in-place, do not allocate extra memory.
11+ Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
12+ 1,2,3 -> 1,3,2
13+ 3,2,1 -> 1,2,3
14+ 1,1,5 -> 1,5,1
15+
16+ Solution: O(n)
17+ Processes: Take A = {1,3,2} as an example:
18+ 1. Traverse from back to forth, find the turning point, that is A[i] = 3.
19+ 2. Sort from the turning point to the end (A[i] to A[end]), so {3,2} becomes {2,3}.
20+ 3. If i equals to 0, finish! Else, goto 4.
21+ 4. Let j = i, search from A[j] to A[end] to find the first elem which is larger than A[i-1], '2' here.
22+ 5. Swap the elem A[j] with A[i-1].
23+ Finally, the next permutation is {2,1,3}.
24+ */
25+
26+ public class Solution {
27+ public void nextPermutation_1 (int []num ) {
28+ int last =num .length -1 ;
29+ int i =last ;
30+ while (i >0 &&num [i -1 ] >=num [i ]) --i ;
31+ if (i ==0 ) {
32+ for (int l =0 ,r =last ;l <r ; ++l , --r ) {
33+ int tmp =num [l ];
34+ num [l ] =num [r ];
35+ num [r ] =tmp ;
36+ }
37+ return ;
38+ }
39+ for (int j =last ;j >=i ; --j ) {
40+ if (num [j ] >num [i -1 ]) {
41+ int tmp =num [j ];
42+ num [j ] =num [i -1 ];
43+ num [i -1 ] =tmp ;
44+ for (int l =i ,r =last ;l <r ; ++l , --r ) {
45+ int t =num [l ];
46+ num [l ] =num [r ];
47+ num [r ] =t ;
48+ }
49+ return ;
50+ }
51+ }
52+ }
53+ public void nextPermutation_2 (int []num ) {
54+ int last =num .length -1 ;
55+ int i =last ;
56+ while (i >0 &&num [i -1 ] >=num [i ]) --i ;
57+ for (int l =i ,r =last ;l <r ; ++l , --r ) {
58+ num [l ] =num [l ] ^num [r ];
59+ num [r ] =num [l ] ^num [r ];
60+ num [l ] =num [l ] ^num [r ];
61+ }
62+ if (i ==0 ) {
63+ return ;
64+ }
65+ int j =i ;
66+ while (j <=last &&num [i -1 ] >=num [j ]) ++j ;
67+ num [i -1 ] =num [i -1 ] ^num [j ];
68+ num [j ] =num [i -1 ] ^num [j ];
69+ num [i -1 ] =num [i -1 ] ^num [j ];
70+ }
71+ }
