题意

在所有不同的组合数值中，求出第 小的值。

解法1： set（TLE+MLE）

注意到 ，因此只需考虑第 行的所有值，输出其中第 大的值即可。

求 一般有如下几种方法（代码中采用了第3种）：

1. 利用公式 直接求。
2. 利用公式 进行递推。
3. 利用公式 进行递推。

由于可能出现重复值（比如 ），因此需要进行去重。

可以用一个 set 进行维护。

代码

class Solution {
public:
    /**
     * 
     * @param k int整型 
     * @return int整型
     */
    int kthSamllest(int k) {
        // write code here
        set<int>s;
        s.insert(1); // C(0,0)
        for(int i = 1; i <= k; i++){
            int cij = 1; // C(i, 0)
            s.insert(cij);
            for(int j = 1; j <= i; j++){
                cij = cij * (i + 1 - j) / j;// C(i, j)
                s.insert(cij);
            }
        }
        auto it = s.begin();
        for(int i = 1; i < k; i++) it++;
        return *it;
    }
};

复杂度分析

空间复杂度：set中元素个数为 ，总复杂度
时间复杂度：组合数递推求出 个元素，每个元素求值复杂度 ，插入复杂度 ，总复杂度

解法2：分析性质

其实我们可以发现 ，因此第 大的组合数就是 。

直接返回 即可。

代码

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

复杂度分析

空间复杂度
时间复杂度