LintCode Q198 Permutation Index II in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2017年2月1日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import math
class Solution:
# @param {int[]} A an integer array
# @return {long} a long integer
def permutationIndexII(self, A):
# Write your code here
index = 1
order = 1
for i in xrange(len(A) - 2, -1, -1):
count = 0
dups = {A[i]: 1}
for j in xrange(i + 1, len(A)):
if A[j] in dups:
dups[A[j]] += 1
else:
dups[A[j]] = 1
if A[i] > A[j]:
count += 1
index += count * order / self.dupPermutaion(dups)
order *= len(A) - i
return index
def dupPermutaion(self, dups):
count = 1
for key in dups:
count *= math.factorial(dups[key])
return count
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。