題目
給出一個不含重復(fù)數(shù)字的排列痪伦，求這些數(shù)字的所有排列按字典序排序后該排列的編號。其中牲蜀，編號從1開始。
樣例
例如在辆，排列 [1,2,4]是第 1個排列。
分析
1.對于四位數(shù)：4213 = 4100+2100+110+3
2.4個數(shù)的排列有4浑度！種箩张。當我們知道第一位數(shù)的時候窗市，還有3！種方式论熙，當知道第二位數(shù)時候還有2脓诡！種方式媒役，當知道第三位數(shù)的時候還有1酣衷！種方式交惯，前面三位數(shù)都確定的時候，最后一位也確定了鸥诽。<這里是按照高位到地位的順序>
3.對4個數(shù)的排列商玫，各位的權(quán)值為：3！牡借，2拳昌！，1钠龙！炬藤，0御铃！。第一位之后的數(shù)小于第一位的個數(shù)是x沈矿，第二位之后的數(shù)小于第二位的個數(shù)是y上真，第三位之后的數(shù)小于第三的個數(shù)是z，第四位之后的數(shù)小于第四位的個數(shù)是w羹膳，則abcd排列所在的序列號:index = x3睡互！+y2!+z1!,<0!=0>
在數(shù)的排列中，小數(shù)在前面，大數(shù)在后面泞歉，所以考慮該位數(shù)之后的數(shù)小于該為的數(shù)的個數(shù)，這里我自己理解的也不是很透挺庞，就這樣宾肺。
4.例如 4213；x= 3增拥，y = 1，z=0猾封，index = 18+2=20
123齐莲；x = 0，y=0芒填，index = 0
321家厌；x= 2，y=1掰吕，index = 22！+11菱属！ = 5
這里的下標是從0開始的。
代碼
public class Solution {
/**
* @param A an integer array
* @return a long integer
*/
public long permutationIndex(int[] permutation) {
// Write your code here
long index = 0;
long position = 2;// position 1 is paired with factor 0 and so is skipped
long factor = 1;
for (int p = permutation.length - 2; p >= 0; p--) {
long successors = 0;
for (int q = p + 1; q < permutation.length; q++) {
if (permutation[p] > permutation[q]) {
successors++;
}
}
index += (successors * factor);
factor *= position;
position++;
}
return index+1;
}
}
