lintcode 197. 排列序号

我不是女神ヾ 2023-07-07 05:52 23阅读 0赞

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

样例
    样例 1:
    
    输入:[1,2,4]
    输出:1
    样例 2:
    
    输入:[3,2,1]
    输出:6

文章参考：https://blog.csdn.net/sinat\_32197439/article/details/60770708  
首先什么是字典排序，比如\[1,2,4\]这个数组的排列方式一共有3!=6种。  
1,2,4  
1,4,2  
2,1,4  
2,4,1  
4,1,2,  
4,2,1  
左边为高位，右边为低位，从左到右都为最小的即第1个排列，这个数组中使1,2,4，他比1,4,2要靠前我们暂时可以理解基本的知识，好为后面的理解打下基础。

2  
.接下来，开始求解某个字典排序是第几个排列了。为了更加直观的看清楚我们选择一个大点的数组\[6,8,4,7,5,3,2\]这个数组，他的第一排序是\[2,3,4,5,6,7,8\]对吧，然后首先拿到待计算排序的第一个元素6，那么在6之前比他小的元素有几个呢？ 是不是有2,3,4,5这4个，确定了第一个元素后，其他剩下的7-1=6个元素进行全排列，共有6！=720种，所以一共有4\*（7-1）！种。但是计算第二个元素的时候要小心了。现在第2个元素是8，比8小的元素有几个呢，6个。错！！！，因为第一个元素已经确定了，所以应该是还有5个，那么此时剩下的元素进行全排列就有5\*（7-2）！种  
下面是每一位上元素的所有排列情况  
6 –> 4x(7-1)!种  
8 –> 5x(7-2)!种  
4 –> 2x(7-3)!种  
7 –> 3x(7-4)!种  
5 –> 2x(7-5)!种  
3 –> 1x(7-6)!种  
2 –> 0x(7-7)!种  
最后再加上一个第1排序，结果就是答案了。。。具体代码如下

class Solution {
        
    public:
        /**
         * @param A: An array of integers
         * @return: A long integer
         */
        long long permutationIndex(vector<int> &A) {
        
            // write your code here
            long long res=1;
            if(A.size()<=0) return res;
            int len=A.size();
            for (int i = 0; i < len; i++) {
        
                long long tmp=0;
                for(int j = i+1 ; j<len ;j++)
                {
        
                    if(A[i]>A[j]) tmp++;
                }
                res=res+tmp*getFactor(len-i-1);
            }
            return res;
        }
        long long getFactor(int n)
        {
        
            long long res=1;
            while(n>=1){
        
                res = res*n;
                n--;
            }
            return res;
        }
    };