Permutation Index

题目描述

given a permutation which contains no repeated number, find its index in all the permutations of these number/characters.

follow up:

has repeated number

解题方法

1

这一题其实跟base number有点像，比如举例356421.

• 对于第一位3， 在它之前的可以有1，2
• 第二位5，在它之前的可以有4，2，1（因为3已经在第二位用了）
• 第三位6，在它之前的可以有4，2，1
• 。。。

而每一位n，在它之前的序列的数量应该是可以替换的数字 * (length - n)!

有重复数字，需要去重

有重复元素就是要去掉重复的排列，排列组合问题，如果我们不在乎n个数字的排列 顺序，那么应该除以n!

所以我们在上面的向右寻找小于自身的数的过程中，要用一个hashmap来记录重复 的数出现的次数，注意

• 自身也要记录
• 对于每个重复的数字，都应该在计算时除以它的出现次数的阶乘

Solution

class Solution:
    # @param A : string
    # @return an integer
    def findRank(self, A):
        if not A:
            return None

        length = len(A)
        result = 1
        factor = 1
        for i in range(length-1, -1, -1):
            numSmaller = 0
            for j in range(i+1, length):
                if A[i] > A[j]:
                    numSmaller += 1
            result += (numSmaller * factor)
            factor *= length - i

        return result

有重复数字的

class Solution:
    # @param A : string
    # @return an integer
    def findRank(self, A):
        if not A:
            return None

        length = len(A)
        result = 1
        factor = 1
        for i in range(length-1, -1, -1):
            dup_dic = {} # 每次都要新建一个新的
            numSmaller = 0
            dup_dic[A[i]] = 1
            for j in range(i+1, length):
                # 所有重复数字都要记录，不仅仅是比它小的
                if A[j] in dup_dic:
                    dup_dic[A[j]] += 1
                else:
                    dup_dic[A[j]] = 1
                if A[i] > A[j]:
                    numSmaller += 1
            result += (numSmaller * factor / self.dupFactor(dup_dic))
            factor *= length - i

        return result % 1000003

    def dupFactor(self, dup_dic):
        result = 1
        if not dup_dic:
            return result
        for num in dup_dic:
            val = dup_dic[num]
            for i in range(1, val+1):
                result *= i
        return result

Reference