【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;
}
Read full article from 【Everyday】(5)排列序号 - Everyday - SegmentFault