树状数组
线段树
数组
二分查找
分治
有序集合
归并排序
题目描述
Given an array perm
of length n
which is a permutation of [1, 2, ..., n]
, return the index of perm
in the lexicographically sorted array of all of the permutations of [1, 2, ..., n]
.
Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: perm = [1,2]
Output: 0
Explanation:
There are only two permutations in the following order:
[1,2]
, [2,1]
And [1,2]
is at index 0.
Example 2:
Input: perm = [3,1,2]
Output: 4
Explanation:
There are only six permutations in the following order:
[1,2,3]
, [1,3,2]
, [2,1,3]
, [2,3,1]
, [3,1,2]
, [3,2,1]
And [3,1,2]
is at index 4.
Constraints:
1 <= n == perm.length <= 105
perm
is a permutation of [1, 2, ..., n]
.
解法
方法一:树状数组
根据题目要求,我们需要找出一共有多少个排列的字典序小于给定的排列。
我们考虑如何计算字典序小于给定排列的排列个数,一共有两种情况:
排列的第一个元素小于 $perm[0]$,一共有 $(perm[0] - 1) \times (n-1)!$ 种排列。
排列的第一个元素等于 $perm[0]$,我们需要继续考虑第二个元素,以此类推。
累加所有情况即可。
我们可以用树状数组维护遍历过的元素中,比当前元素小的元素个数,那么对于给定排列的第 $i$ 个元素,剩余的比它小的元素个数为 $perm[i] - 1 - tree.query(perm[i])$,排列种类数为 $(perm[i] - 1 - tree.query(perm[i])) \times (n-i-1)!$,累加到答案中。然后我们更新树状数组,将当前元素加入树状数组。继续遍历下一个元素,直到遍历完所有元素。
时间复杂度 $O(n \times \log n)$,空间复杂度 $O(n)$。其中 $n$ 为排列的长度。
Python3 Java C++ Go TypeScript
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
30
31
32
33 class BinaryIndexedTree :
__slots__ = "n" , "c"
def __init__ ( self , n : int ):
self . n = n
self . c = [ 0 ] * ( n + 1 )
def update ( self , x : int , delta : int ) -> None :
while x <= self . n :
self . c [ x ] += delta
x += x & - x
def query ( self , x : int ) -> int :
s = 0
while x :
s += self . c [ x ]
x -= x & - x
return s
class Solution :
def getPermutationIndex ( self , perm : List [ int ]) -> int :
mod = 10 ** 9 + 7
ans , n = 0 , len ( perm )
tree = BinaryIndexedTree ( n + 1 )
f = [ 1 ] * n
for i in range ( 1 , n ):
f [ i ] = f [ i - 1 ] * i % mod
for i , x in enumerate ( perm ):
cnt = x - 1 - tree . query ( x )
ans += cnt * f [ n - i - 1 ] % mod
tree . update ( x , 1 )
return ans % mod
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43 class BinaryIndexedTree {
private int n ;
private int [] c ;
public BinaryIndexedTree ( int n ) {
this . n = n ;
this . c = new int [ n + 1 ] ;
}
public void update ( int x , int delta ) {
for (; x <= n ; x += x & - x ) {
c [ x ] += delta ;
}
}
public int query ( int x ) {
int s = 0 ;
for (; x > 0 ; x -= x & - x ) {
s += c [ x ] ;
}
return s ;
}
}
class Solution {
public int getPermutationIndex ( int [] perm ) {
final int mod = ( int ) 1e9 + 7 ;
long ans = 0 ;
int n = perm . length ;
BinaryIndexedTree tree = new BinaryIndexedTree ( n + 1 );
long [] f = new long [ n ] ;
f [ 0 ] = 1 ;
for ( int i = 1 ; i < n ; ++ i ) {
f [ i ] = f [ i - 1 ] * i % mod ;
}
for ( int i = 0 ; i < n ; ++ i ) {
int cnt = perm [ i ] - 1 - tree . query ( perm [ i ] );
ans = ( ans + cnt * f [ n - i - 1 ] % mod ) % mod ;
tree . update ( perm [ i ] , 1 );
}
return ( int ) ans ;
}
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 class BinaryIndexedTree {
private :
int n ;
vector < int > c ;
public :
BinaryIndexedTree ( int n )
: n ( n )
, c ( n + 1 ) {}
void update ( int x , int delta ) {
for (; x <= n ; x += x & - x ) {
c [ x ] += delta ;
}
}
int query ( int x ) {
int s = 0 ;
for (; x > 0 ; x -= x & - x ) {
s += c [ x ];
}
return s ;
}
};
class Solution {
public :
int getPermutationIndex ( vector < int >& perm ) {
const int mod = 1e9 + 7 ;
using ll = long long ;
ll ans = 0 ;
int n = perm . size ();
BinaryIndexedTree tree ( n + 1 );
ll f [ n ];
f [ 0 ] = 1 ;
for ( int i = 1 ; i < n ; ++ i ) {
f [ i ] = f [ i - 1 ] * i % mod ;
}
for ( int i = 0 ; i < n ; ++ i ) {
int cnt = perm [ i ] - 1 - tree . query ( perm [ i ]);
ans += cnt * f [ n - i - 1 ] % mod ;
tree . update ( perm [ i ], 1 );
}
return ans % mod ;
}
};
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
30
31
32
33
34
35
36
37
38
39 type BinaryIndexedTree struct {
n int
c [] int
}
func NewBinaryIndexedTree ( n int ) * BinaryIndexedTree {
return & BinaryIndexedTree { n : n , c : make ([] int , n + 1 )}
}
func ( bit * BinaryIndexedTree ) update ( x , delta int ) {
for ; x <= bit . n ; x += x & - x {
bit . c [ x ] += delta
}
}
func ( bit * BinaryIndexedTree ) query ( x int ) int {
s := 0
for ; x > 0 ; x -= x & - x {
s += bit . c [ x ]
}
return s
}
func getPermutationIndex ( perm [] int ) ( ans int ) {
const mod int = 1e9 + 7
n := len ( perm )
tree := NewBinaryIndexedTree ( n + 1 )
f := make ([] int , n )
f [ 0 ] = 1
for i := 1 ; i < n ; i ++ {
f [ i ] = f [ i - 1 ] * i % mod
}
for i , x := range perm {
cnt := x - 1 - tree . query ( x )
ans += cnt * f [ n - 1 - i ] % mod
tree . update ( x , 1 )
}
return ans % mod
}
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
30
31
32
33
34
35
36
37
38
39
40 class BinaryIndexedTree {
private n : number ;
private c : number [];
constructor ( n : number ) {
this . n = n ;
this . c = Array ( n + 1 ). fill ( 0 );
}
update ( x : number , delta : number ) : void {
for (; x <= this . n ; x += x & - x ) {
this . c [ x ] += delta ;
}
}
query ( x : number ) : number {
let s = 0 ;
for (; x > 0 ; x -= x & - x ) {
s += this . c [ x ];
}
return s ;
}
}
function getPermutationIndex ( perm : number []) : number {
const mod = 1e9 + 7 ;
const n = perm . length ;
const tree = new BinaryIndexedTree ( n + 1 );
let ans = 0 ;
const f : number [] = Array ( n ). fill ( 1 );
for ( let i = 1 ; i < n ; ++ i ) {
f [ i ] = ( f [ i - 1 ] * i ) % mod ;
}
for ( let i = 0 ; i < n ; ++ i ) {
const cnt = perm [ i ] - 1 - tree . query ( perm [ i ]);
ans = ( ans + cnt * f [ n - i - 1 ]) % mod ;
tree . update ( perm [ i ], 1 );
}
return ans % mod ;
}
GitHub