Lintcode198 Permutation Index II solution 题解
发布在LINTCODE2018年2月3日view:305移动开发
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Given a permutation which may contain repeated numbers, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

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

【题目链接】

www.lintcode.com/en/problem/permutation-index-ii/

【题目解析】

这道题和Permutation IndexI思想一样,计算每一位上数字是该位上第几个排列,再将每一位结果加和即可。只是这道题有重复元素,有无重复元素最大的区别在于原来的1!, 2!, 3!…等需要除以重复元素个数的阶乘。按照数字从低位到高位进行计算。每遇到一个重复的数字就更新重复元素个数的阶乘的值。

从后往前遍历数组,用一个hashmap来记录重复元素个数。若新来的数不是重复元素,则加入hashmap,否则将重复元素个数+1,同时更新重复元素个数的阶乘。

比较当前位和其后面位的数,计算当前位是第几大的数count

当前位的index为:2的结果count * 其后面位数的阶乘/重复数个数的阶乘。将当前位计入阶乘,重复1-3计算前一位。

注意:1.题目说index从1开始算。2.要用long来保存index,fact和muitlFact,用int有可能超过范围

【参考答案】

www.jiuzhang.com/solutions/permutation-index-ii/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏