【Everyday】(5)排列序号 - Everyday

问题描述

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

样例
例如，排列[1,2,4]是第1个排列

解题思路

给出一个数组，数组中的元素全部都是不相同的，首先要解决的是对该数组中的序列进行全排列，然后按照字典排序后的位置对其编号，然后再和最开始的进行一个比对，确定这是第一个，首先想到的是全排列规则，如果按照复杂度最高的，则是通过阶乘获得其所有的序列，然后根据我们的序列和其比对，确定其编号是多少，这肯定是不符号要求的，其中肯定是含有某种规律，需要我们通过寻找规律来有效的降低复杂度来解决问题，想象阶乘的结构，某一个位置的序号应该是后面比其小的数字，减去当前位，将后面的位数进行全排列后加1得到，按照这种思路我们得到一个o(n^2)复杂度的算法。

代码实现

public long permutationIndex(int[] A) {        // Write your code here        long number = 0;        if(A==null||A.length==0)return number;        for(int i=0;i<A.length-1; i++){int tmp=0;for(int j=i+1;j<A.length; j++){    if(A[j]<A[i])        tmp++;}number+=tmp*getFacResult(A.length-i-1);        }        return ++number;    }    public long getFacResult(int n){        long result=1;        while(n>=1){result = result*n;n--;        }        return result;    }

优化与启发

1.通过几个题目的锻炼，总结出来的规律是对于问题进行仔细的分析，找出一个普遍的规律，然后将这个规律通过编程进行表达。
2.在这里出现了一个问题是对于阶乘的值开始通过int表达，然后出现了错误，转为long后问题解决，这个需要在编程中要考虑到了。