题目描述

大意：求解第$kk$k小的组合数

算法一：set+组合数

算法思路

• 以下是1-12的组合数的图

• 通过图片我们可以发现$C(i,0)=C(i,i)=1C(i,0)=C(i,i)=1$C(i,0)=C(i,i)=1
• 因为还有的组合数重复，所以我们用$setset$set来去重
• 故我们可以用一个$setset$set来维护这些组合数的大小，但是计算的时候就不重复插入$11$1
• 将所有的组合数插入到$setset$set中，最后返回$setset$set中第$kk$k小的数
• 计算组合数时，我们只需要计算底数$\le i\backslash leq\; i$≤i的即可
• 求解单个组合数，$C_n^{k}C\_n^k$Cnk​分子分母约分后，可以在$O\left(k\right)O(k)$O(k)的复杂度求出来

代码实现

class Solution {
public:
  int C(int n, int k) //计算组合数C(n,k)，n个里面取k个
  {//时间复杂度O(k)
      long long res = 1;
      for (int i = n; i >= n - k + 1; i -- ) //计算分子
          res *= i;
      for (int i = 1; i <= k; i ++ ) //除去分母
          res /= i;
      return res; //返回答案
  }
  int kthSamllest(int k) {
      set<int> s;
      s.insert(1);
      for (int i = 2; i <= k; i ++ ) //插入所有底小于等于k的组合数
          for (int j = 1; j <= i / 2; j ++ ) //C(i,0)=C(i,i)=1
            //故不需要重复插
              s.insert(C(i,j));
      int cnt = 0;
      for(auto it : s)
      {
          cnt ++ ;
          if(cnt == k) return it; //第k小的组合数
      }
      return 0;
  }
};

复杂度分析

• 时间复杂度，求解单个组合数的时间复杂度为$O\left(j\right)O(j)$O(j)，对于数$ii$i，需要求解${\displaystyle \frac{i}{2}}\backslash cfrac\{i\}\{2\}$2i​个组合数，${\sum }_{i=2}^k{\sum }_{j=1}^{\lfloor {\displaystyle \frac{i}{2}}\rfloor }j=2{\sum }_{i=1}^{k}i(k-i)=2k\sum i-2\sum i^2=2k\ast {\displaystyle \frac{k(k+1)}{2}}-2\ast {\displaystyle \frac{k(k+1)(2k+1)}{6}}=O\left(k^3\right)\backslash sum\_\{i=2\}^\{k\}\; \backslash sum\_\{j=1\}^\{\backslash lfloor\; \backslash cfrac\{i\}\{2\}\backslash rfloor\}\; j=2\backslash sum\_\{i=1\}^\{k\}i(k-i)=2k\backslash sum\; i\; -\; 2\backslash sum\; i^2=2k*\backslash cfrac\{k(k+1)\}\{2\}-2*\backslash cfrac\{k(k+1)(2k+1)\}\{6\}=O(k^3)$∑i=2k​∑j=1⌊2i​⌋​j=2∑i=1k​i(k−i)=2k∑i−2∑i2=2k∗2k(k+1)​−2∗6k(k+1)(2k+1)​=O(k3)，计算所有的组合数的时间复杂度为$O\left(k^3\right)O(k^3)$O(k3)，$setset$set中插入的复杂度为$\log n\backslash log\; n$logn，所以将所有组合数放入set中的复杂度为$O(k^3\log k^3)=O(3k^3\log k)=O(k^3\log k)O(k^3\; \backslash log\; k^3)=O(3k^3\; \backslash log\; k)=O(k^3\; \backslash log\; k)$O(k3logk3)=O(3k3logk)=O(k3logk)，set中查询的复杂度为$O(\log n)O(\backslash log\; n)$O(logn)，但是遍历的复杂度为$O\left(n\right)O(n)$O(n)，我们只遍历了前$kk$k个数，所以时间复杂度为$O\left(k\right)O(k)$O(k)，总得时间复杂度为$O(k^3\log k+k)=O(k^3\log k)O(k^3\backslash log\; k+k)=O(k^3\backslash log\; k)$O(k3logk+k)=O(k3logk)级别
• 空间复杂度，为set内元素的规模，为$O\left(k^3\right)O(k^3)$O(k3)级别。

算法二：数学分析法

算法思路

• 我们再仔细分析这张图片………………
• 其实这题很好发现$C_k^1=C_k^{k-1}=kC\_k^1=C\_k^\{k-1\}=k$Ck1​=Ckk−1​=k
• 所以，其实我们直接return k;即可

代码实现

class Solution {
public:
    int kthSamllest(int k) {
        return k;
    }
};

复杂度分析

• 时间复杂度，$O\left(1\right)O(1)$O(1)
• 空间复杂度，$O\left(1\right)O(1)$O(1).