| comments | difficulty | edit_url | tags | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
|
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 <= 105permis a permutation of[1, 2, ..., n].
According to the problem requirements, we need to find out how many permutations are lexicographically smaller than the given permutation.
We consider how to calculate the number of permutations that are lexicographically smaller than the given permutation. There are two situations:
- The first element of the permutation is less than
$perm[0]$ , there are$(perm[0] - 1) \times (n-1)!$ permutations. - The first element of the permutation is equal to
$perm[0]$ , we need to continue to consider the second element, and so on. - The sum of all situations is the answer.
We can use a binary indexed tree to maintain the number of elements that are smaller than the current element in the traversed elements. For the
The time complexity is
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 % modclass 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;
}
}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;
}
};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
}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;
}