首页 > 编程学习 > 【Lintcode】198. Permutation Index II

【Lintcode】198. Permutation Index II

发布时间:2022/11/6 8:57:39

题目地址:

https://www.lintcode.com/problem/198/description

给定一个 1 ∼ n 1\sim n 1n的长 m m m的可重复排列 A A A,问该排列的字典序。字典序按从小到大排,并且计数从 1 1 1开始。

思路和https://blog.csdn.net/qq_46105170/article/details/108544398差不多,不同的是本题每个数字可能有重复。回忆一下无重复数的全排列的康托展开。康托展开 f f f是从一个全排列到其字典序排名的一个映射(这个排名是从 0 0 0开始的)。对于一个全排列 X = ( x 1 , x 2 , . . . , x n ) X=(x_1,x_2,...,x_{n}) X=(x1,x2,...,xn),有: f ( X ) = a 1 ( n − 1 ) ! + a 2 ( n − 2 ) ! + . . . + a n 0 ! f(X)={a_1}(n-1)!+a_{2}(n-2)!+...+a_n0! f(X)=a1(n1)!+a2(n2)!+...+an0!其中 a i a_i ai指的是 x i x_i xi右边比 x i x_i xi小的数的个数。对于 a 1 ( n − 1 ) ! a_1(n-1)! a1(n1)!可以这么想, x 1 x_1 x1后面有 a 1 a_1 a1个数比它小,将比 x 1 x_1 x1小的数换到 x 1 x_1 x1的位置之后,产生的所有全排列都比 X X X小,从而其排名应该加上 a 1 ( n − 1 ) ! a_1(n-1)! a1(n1)!

类似地,当有重复数字的时候,我们也同样考虑, x 1 x_1 x1后面有 a 1 a_1 a1个数比它小,将比 x 1 x_1 x1小的数换到 x 1 x_1 x1的位置之后,产生的全排列有 a 1 ( n − 1 ) ! a_1(n-1)! a1(n1)!个,但是这是不考虑重复的,如果考虑重复,例如我们发现 3 3 3这个数出现了 k 3 k_3 k3次,那么这 k 3 k_3 k3 3 3 3的全排列本质上都是一样的,从而要除掉。令 g i = ∏ s ≤ x i k 1 ! k 2 ! . . . k s ! g_i=\prod_{s\le x_i} k_1!k_2!...k_s! gi=sxik1!k2!...ks! k i k_i ki i i i这个数字重复出现了多少次,那么修正之后的公式为: f ( X ) = a 1 ( n − 1 ) ! g 1 + a 2 ( n − 2 ) ! g 2 + . . . + a n 0 ! f(X)={a_1}\frac{(n-1)!}{g_1}+a_{2}\frac{(n-2)!}{g_2}+...+a_n0! f(X)=a1g1(n1)!+a2g2(n2)!+...+an0!

代码如下:

class Solution {
public:
  /**
   * @param a: An array of integers
   * @return: A long integer
   */
  vector<int> tr;
  int n;
#define lowbit(x) (x & -x)

  void add(int k, int x) {
    for (; k <= n; k += lowbit(k)) tr[k] += x;
  }

  int sum(int k) {
    int res = 0;
    for (; k; k -= lowbit(k)) res += tr[k];
    return res;
  }

  using LL = long long;
  LL permutationIndexII(vector<int> &a) {
    // write your code here
    n = *max_element(a.begin(), a.end());
    tr.resize(n + 1);
    LL res = 0, fact = 1, mult = 1;
    // mp记录每个数的重复度
    unordered_map<int, int> mp;
    for (int i = a.size() - 1; i >= 0; i--) {
      mp[a[i]]++;
      mult *= mp[a[i]];
      add(a[i], 1);
      res += fact * sum(a[i] - 1) / mult;
      fact *= a.size() - i;
    }

    return res + 1;
  }
};

时间复杂度 O ( m log ⁡ n ) O(m\log n) O(mlogn),空间 O ( n ) O(n) O(n)

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式