lintcode Permutation Index

简介:

 题目: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;
    }
};
复制代码

 

目录
相关文章
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。
104 0
LeetCode 378. Kth S Element in a Sorted Matrix
LeetCode 60. Permutation Sequence
集合[1,2,3,...,n]总共包含n的阶乘个独特的排列。
71 0
LeetCode 60. Permutation Sequence
|
算法
[LeetCode]--60. Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): 1."123" 2."132" 3
1077 1
|
人工智能 C++ 索引