lintcode ：Permutation Index 排列序号

题目：

排列序号

给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。

样例

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

解题：

这个题目感觉很坑的。感觉这只有求出所有的排列，然后找出其对应的下标，但是怎么求出排列，在做Project Euler 时候碰到过，但是现在我又不会写了，那时候毕竟是抄别人的程序的。在geekviewpoint看到一种很厉害的解法，不需要求所有的排列，直接根据给的数组进行求解。

思路：

1.对于四位数：4213 = 4*100+2*100+1*10+3

2.4个数的排列有4！种。当我们知道第一位数的时候，还有3！种方式，当知道第二位数时候还有2！种方式，当知道第三位数的时候还有1！种方式，前面三位数都确定的时候，最后一位也确定了。<这里是按照高位到地位的顺序>

3.对4个数的排列，各位的权值为：3！，2！，1！，0！。第一位之后的数小于第一位的个数是x，第二位之后的数小于第二位的个数是y，第三位之后的数小于第三的个数是z，第四位之后的数小于第四位的个数是w，则abcd排列所在的序列号:index = x*3！+y*2!+z*1!,<0!=0>

在数的排列中，小数在前面，大数在后面，所以考虑该位数之后的数小于该为的数的个数，这里我自己理解的也不是很透，就这样。

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 = 2*2！+1*1！ = 5

这里的下标是从0开始的。

Java程序：

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++;

    }

    index = index + 1;

    return index;

    }

}

总耗时: 5756 ms

Python程序：

class Solution:

    # @param {int[]} nums an integer array

    # @return {long} a long integer

    def permutationIndex(self, nums):

        # Write your code here

        index = 0

        position  = 2

        factor = 1

        numslen = len(nums)

        for i in range((numslen-2),-1,-1):

            successors = 0

            for j in range((i+1),numslen):

                if nums[i]>nums[j]:

                    successors+=1

            index += successors*factor

            factor*=position

            position+=1

        index +=1

        return index

总耗时: 223 ms

同时，九章上面的程序还看不懂。。。

巴特西

lintcode ：Permutation Index 排列序号

排列序号

最新文章

热门文章