宁波外贸公司网站建设,保定seo推广公司,网站主机免备案,做外贸网站效果图题目#xff1a;http://www.lintcode.com/zh-cn/problem/permutation-index/ 排列序号 给出一个不含重复数字的排列#xff0c;求这些数字的所有排列按字典序排序后该排列的编号。其中#xff0c;编号从1开始。 样例 例如#xff0c;排列[1,2,4]是第1个排列。 思路#xf… 题目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对应的基数分别是3210(0!0)。 d.得到该位置对应的基数后那么该位置对应多少个可变数字9所在位置对应的可变数字的个数为4分别是5,4,1,2 5所在位置对应的可变数字是4,1,24所在位置对应的可变数字是1,2,1所在位置的对应的可变数字:无。2所在位置 对应可变数也是无。 e.可以得到结论X全排列某个位置上对应的可变数字的个数 这个数后面有多少个比它小的数的个数。 f.为了得到某个数后面有多少个比它小的数的个数我们采用折半插入排序从后向前插入。 class Solution {
public:/*** param A an integer array* return a long integer*/long long permutationIndex(vectorint A) {// Write your code here//阿欧知道会超时试一试还真tm超时// vectorint permu(A.begin(), A.end());// sort(permu.begin(), permu.end());// int cnt 0;// do{// int i;// for(i0; iA.size(); i)// if(A[i]!permu[i])// break;// cnt;// if(iA.size()) break;// }while(next_permutation(permu.begin(), permu.end()));// return cnt;vectorint a;int len A.size();int cnt[len];cnt[len-1] 0;a.push_back(A[len-1]);for(int ilen-2; i0; --i){//统计每个数后面有多少个比它小的数的个数vectorint::iterator it lower_bound(a.begin(), a.end(), A[i]);cnt[i] it-a.begin();a.insert(it, A[i]);}long long ans1, fac1, c1;//基数fac从1开始for(int ilen-2; i0; --i)ans (fac*c)*cnt[i];return ans;}
}; 转载于:https://www.cnblogs.com/hujunzheng/p/5020211.html
