题解 | #组合数第k小#

题意

给定一个整数k，返回第k小的组合数.

方法一（暴力方法）

我们直接计算杨辉三角。（这里用到了set,可以排除掉重复的结果）

应该按照递推的方式，计算出大量的值，再进行排序，获得第k小的答案。

class Solution {
public:
    /**
     * 
     * @param k int整型 
     * @return int整型
     */
    int yh [5000][5000];
    int kthSamllest(int k) { 
        set<int> num;
        for (int i = 0;i <= 20;++ i) {
            for (int j = 0;j < i;++ j) {
                if (j == 0 || i == j) {
                    yh [i][j] = 1;
                } else {
                    yh [i][j] = yh [i - 1][j] + yh [i - 1][j - 1];
                }
                num.insert(yh [i][j]);
            }
        }
        int cnt = 0;
        for (auto &e:num) {
            ++cnt;
            if (cnt == k) {
                return e;
            }
        }
        return 0;
    }
};

因为 ，而我们所计算的组合数数量显然远小于k，更不用提去重后的数字数量了。
时间复杂度和空间复杂度都无比巨大。复杂度根据方法二的分析可得，为

方法二 (正解)

因为题目要求给出第k小的组合数，那么对于重复的数字不用考虑。
而我们知道杨辉三角中所有的数字都是正数，且有公式 ,所以1-k之间的k个数都可以取到。那么显然，第k小的数就是k。

class Solution {
public:
    /**
     * 
     * @param k int整型 
     * @return int整型
     */
    int kthSamllest(int k) { 
        return k;
    }
};

因为直接返回k，所以时间复杂度与空间复杂度都是