【題目描述】
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.
給出一個(gè)可能包含重復(fù)數(shù)字的排列扑浸，求這些數(shù)字的所有排列按字典序排序后該排列在其中的編號(hào)启昧。編號(hào)從1開始。
【題目鏈接】
www.lintcode.com/en/problem/permutation-index-ii/
【題目解析】
這道題和Permutation IndexI思想一樣，計(jì)算每一位上數(shù)字是該位上第幾個(gè)排列，再將每一位結(jié)果加和即可哮笆。只是這道題有重復(fù)元素凛膏，有無重復(fù)元素最大的區(qū)別在于原來的1!, 2!, 3!...等需要除以重復(fù)元素個(gè)數(shù)的階乘神僵。按照數(shù)字從低位到高位進(jìn)行計(jì)算腿宰。每遇到一個(gè)重復(fù)的數(shù)字就更新重復(fù)元素個(gè)數(shù)的階乘的值弟蚀。
從后往前遍歷數(shù)組，用一個(gè)hashmap來記錄重復(fù)元素個(gè)數(shù)酗失。若新來的數(shù)不是重復(fù)元素，則加入hashmap昧绣，否則將重復(fù)元素個(gè)數(shù)＋1规肴，同時(shí)更新重復(fù)元素個(gè)數(shù)的階乘。
比較當(dāng)前位和其后面位的數(shù)，計(jì)算當(dāng)前位是第幾大的數(shù)count
當(dāng)前位的index為：2的結(jié)果count * 其后面位數(shù)的階乘/重復(fù)數(shù)個(gè)數(shù)的階乘拖刃。將當(dāng)前位計(jì)入階乘删壮，重復(fù)1-3計(jì)算前一位。
注意：1.題目說index從1開始算兑牡。2.要用long來保存index央碟，fact和muitlFact，用int有可能超過范圍
【參考答案】
