LeetCode Online Judge 题目C# 练习 - Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

 1         public static void NextPermutation(List<int> num)
 2         {
 3             if (num.Count <= 1)
 4                 return;
 5 
 6             //find the falling edge
 7             int edge = -1;
 8             for (int i = num.Count - 2; i >= 0; i--)
 9             {
10                 if (num[i] < num[i + 1])
11                 {
12                     edge = i;
13                     break;
14                 }
15             }
16 
17             if (edge > -1)
18             {
19                 //find replacement
20                 for (int i = edge + 1; i < num.Count; i++)
21                 {
22                     if (num[edge] >= num[i])
23                     {
24                         NextPermutationSwap(num, edge, i - 1);
25                         break;
26                     }
27                     if (i == num.Count - 1)
28                     {
29                         NextPermutationSwap(num, edge, i);
30                         break;
31                     }
32                 }
33             }
34 
35             //reverse the following elements
36             for(int i = edge + 1, j = num.Count - 1; i <= edge + (num.Count - edge - 1) / 2; i++, j--)
37             {
38                 NextPermutationSwap(num, i, j);
39             }
40         }
41 
42         //swap helper function
43         public static void NextPermutationSwap(List<int> num, int i, int j)
44         {
45             int temp = num[i];
46             num[i] = num[j];
47             num[j] = temp;
48         }

代码分析：

　　O(n)， 其实也是BF而已，主要是找到做的方法。

　　分三步：

　　1. 从后往前找falling edge，下降沿。（下降之后的那个元素）

　　2. 从下降沿开始往后找出替换它的元素。（就是第一个比它小的前一个元素）

　　3. 反转后面所有元素，让他从小到大sorted（因为之前是从大到小sorted的）

　　例如 “547532“

　　1. “547532”， 4是下降沿。

　　2. “547532”， 5是要替换的元素， 替换后得到 “ 557432”

3. "557432", 7432反转，得到 “552347”。