next-permutation-ii&&permutation-index-ii

1、下一个排列

给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。

如果没有下一个排列，则输出字典序最小的序列。

样例

左边是原始排列，右边是对应的下一个排列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

挑战

不允许使用额外的空间。

不得不吐槽，我竟然花了一个多小时来写这道题，为什么呢？因为首先不知道如何去找下一个排列，想了好久，其中有两个不完全正确的算法指导我分别卡在了28%和49%。。。然后手懒的我为了省力气少编写一个函数，选择了C++，深深的被C++的return教训了一番。

算法：这道题据说也是经典面试题目之一。本质都是字典排序的变形。

字典序法的描述如下：

        设P是1～n的一个全排列:p=p[1]p[2]......p[n]=p[1]p[2]......p[j-1]p[j]p[j+1]......pn
   1）从排列的右端(n)开始，找出第一个比相邻右边字符小的字符的序号j（j从左端开始计算），即 j=max{i|p[i]<p[i+1]}
   2）在p[j]的右边的字符中，找出所有比p[j]大的字符中最小的字符p[k]，即从右端开始的第一个比p[j]大的；（右边的字符从右至左是递增的，因此k是所有大于pj的字符中序号最大者）
   3）对换pj，pk
   4）再将pj+1......pk-1pkpk+1pn倒转得到排列p''=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。

 1 class Solution {
 2 public:
 3     /**
 4      * @param nums: a vector of integers
 5      * @return: return nothing (void), do not return anything, modify nums in-place instead
 6      */
 7     void nextPermutation(vector<int> &nums) {
 8         // write your code here
 9         int len = nums.size();
10         int i=len-1;
11         while (i>0 && nums[i-1]>=nums[i]){
12             i--;
13         }
14         if (i == 0)  {
15             reverse(nums.begin(),nums.end());
16             return;
17         }
18         for(int j = len-1;j>i-1;j--){
19             if(nums[i-1]<nums[j]){
20                 int temp = nums[i-1];
21                 nums[i-1]=nums[j];
22                 nums[j]=temp;
23                 reverse(nums.begin()+i,nums.end());
24                 return;
25             }
26         }
27     }
28 };

好吧，我为了省事利用C++中的reverse函数，可是我竟然不知道C++中的无返回的retrun相当于break，随便添加return 的人华丽丽的调试了10多分钟。

2、排列序号II

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。

样例

给出排列[1, 4, 2, 2]，其编号为3。

 1 public class Solution {
 2     /**
 3      * @param A
 4      *            an integer array
 5      * @return a long integer
 6      */
 7     long fac(int numerator) {
 8             
 9         long now = 1;
10         for (int i = 1; i <= numerator; i++) {
11             now *= (long) i;
12         }
13         return now;
14     }
15     long generateNum(HashMap<Integer, Integer> hash) {
16         long denominator = 1;
17         int sum = 0;
18         for (int val : hash.values()) {
19             if(val == 0 )    
20                 continue;
21             denominator *= fac(val);
22             sum += val;
23         }
24         if(sum==0) {
25             return sum;
26         }
27         return fac(sum) / denominator;
28     }
29 
30     public long permutationIndexII(int[] A) {
31         HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
32         
33         for (int i = 0; i < A.length; i++) {
34             if (hash.containsKey(A[i]))
35                 hash.put(A[i], hash.get(A[i]) + 1);
36             else {
37                 hash.put(A[i], 1);
38             }
39         }
40         long ans = 0;
41         for (int i = 0; i < A.length; i++) {
42             HashMap<Integer, Integer> flag = new HashMap<Integer, Integer>();
43             
44             for (int j = i + 1; j < A.length; j++) {
45                 if (A[j] < A[i] && !flag.containsKey(A[j])) {
46                         flag.put(A[j], 1);
47                 
48                     hash.put(A[j], hash.get(A[j])-1);
49                     ans += generateNum(hash);
50                     hash.put(A[j], hash.get(A[j])+1);
51                     
52                 }
53             
54             }
55                 hash.put(A[i], hash.get(A[i])-1);
56         }
57         
58         return ans+1;
59 
60     }
61 }