题目:http://www.lintcode.com/zh-cn/problem/permutation-index/
排列序号
给出一个不含重复数字的排列,求这些数字的所有排列按字典序排序后该排列的编号。其中,编号从1开始。
样例
例如,排列[1,2,4]是第1个排列。
思路:
1.直接暴力,利用c++中
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
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/225378
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!