?題目：http://www.lintcode.com/zh-cn/problem/permutation-index/

排列序號

給出一個不含重復數字的排列，求這些數字的所有排列按字典序排序后該排列的編號。其中，編號從1開始。

樣例

例如，排列[1,2,4]是第1個排列。

思路：

1.直接暴力，利用c++中<algorithm>中的next_permutation()方法不斷的尋找下一個全排列，直到相等為止！

2.首先觀察一個全排列， 例如：95412 = X

　　a.題目轉換成按照字典序，這個全排列之前有多少個全排列。

　　b.X的前面的所有全排列中，對于位置1上可以是5, 4, 1, 2任意一個數，而且對應的全排列的基數都是4!個。

　　c.同理位置2, 3, 4, 5對應的基數分別是，3！，2！，1！，0！(0!==0)。

　　d.得到該位置對應的基數后，那么該位置對應多少個可變數字？9所在位置對應的可變數字的個數為4，分別是5,4,1,2；

　　　5所在位置對應的可變數字是4,1,2；4所在位置對應的可變數字是1,2,；1所在位置的對應的可變數字:無。2所在位置

　　 ? 對應可變數也是無。

　　e.可以得到結論，X全排列某個位置上對應的可變數字的個數 == 這個數后面有多少個比它小的數的個數。

　　f.為了得到某個數后面有多少個比它小的數的個數，我們采用折半插入排序（從后向前插入）。

class Solution { public:/*** @param A an integer array* @return a long integer*/long long permutationIndex(vector<int>& A) {// Write your code here//阿歐，知道會超時，試一試還真tm超時// vector<int> permu(A.begin(), A.end());// sort(permu.begin(), permu.end());// int cnt = 0;// do{// int i;// for(i=0; i<A.size(); ++i)// if(A[i]!=permu[i])// break;// ++cnt;// if(i>=A.size()) break;// }while(next_permutation(permu.begin(), permu.end()));// return cnt; vector<int> a;int len = A.size();int cnt[len];cnt[len-1] = 0;a.push_back(A[len-1]);for(int i=len-2; i>=0; --i){//統計每個數后面有多少個比它小的數的個數vector<int>::iterator it = lower_bound(a.begin(), a.end(), A[i]);cnt[i] = it-a.begin();a.insert(it, A[i]);}long long ans=1, fac=1, c=1;//基數fac從1開始for(int i=len-2; i>=0; --i)ans += (fac*=c++)*cnt[i];return ans;} };

?

轉載于:https://www.cnblogs.com/hujunzheng/p/5020211.html

總結

以上是生活随笔為你收集整理的lintcode Permutation Index的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。