【Everyday】(5)排列序号 - Everyday - SegmentFault
给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。
给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从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;
}