题解 | NC605 #组合数第k小#

题目描述

在所有不同的组合数值中，第k小的组合数值是多少呢。给定一个k，返回第k小的组合数值。
示例1
输入：1
返回值：1
说明：最小的的组合数是

题目分析

组合数的概念是在给定的 n 个元素中取出 m 个元素，不考虑元素排序的组合个数，表示为；
计算组合数的数学公式为：
其中，n和m都可以从0开始，一直到限制的大小，想要获得第k小的组合数，可以获取到范围比k大的组合数，然后按照从小到大的顺序取出第k个。
想要获取组合数，可以将n和m，分别枚举，根据公式求组合数值，不过这样做的时间花费比较多，容易超时。

解题思路

方法1：统计k范围内的所有组合数，按顺序取出第k小的数
求组合数的过程如下：

fn(m,n){
  for(int i=1;i<=n;i++){
    for(int j=1;j<=i/2;j++){
        // 根据公式求C(j,i)，将结果存储
        // 根据组合特性可知C(j,i) = C(i-j,i)（取出1个和取出n-1个数的组合数相同），所以j只需要枚举到i的一半即可
    }
  }
}

方法2：数学分析
根据组合数中的特例：，因为组合数都是正整数（组合方法的个数），又根据特例可知组合数组成的正整数可以连续，所以易知第k小的数，就是k。

代码实现

方法1：统计k范围内的所有组合数，按顺序取出第k小的数

    public int kthSamllest (int k) {
        // write code here
        if(k==1) return 1;
        // 使用有顺序存储的set
        TreeSet<Integer> set = new TreeSet<>();
        set.add(1);
        // 枚举所有的组合数
        // i是组合元素总数
        for(int i=1;i<=k;i++){
            // j是从i中取出的元素数, C(j,i) = C(i-j, i)，只需要遍历一半
            for(int j=1;j<=i/2;j++){
                int num = C(i,j);
                if(!set.contains(num)){
                    set.add(num);
                }
            }
        }
        int res = 0;
        // 取出前k个数
        for(Integer num :set){
            if(k == 1){
                // 记录第k个数
                res = (int)num;
                break;
            }
            k--;
        }
        return res;
    }

    public int C(int n, int m){
        // C(m,n) = (n*(n-1)*..(n-m+1))/(m!)
        int res = 1;
        // 计算分子
        for(int i=n-m+1;i<=n;i++){
            res *= i;
        }
        // 计算分母
        for(int i=1;i<=m;i++){
            res /= i;
        }
        return res;
    }

时间复杂度：，因为在计算组合数的过程中，使用到了三层循环，第一层循环次数为k，第二层为k/2，第三层为 k（2*k/2=k），循环总次数为；
空间复杂度：，使用的额外空间是set中存储的组合数，虽然有重复的数不会重复存储，但接近;

方法2：数学分析

public int kthSamllest (int k) {
    return k;
}

时间复杂度：，可以直接返回结果；
空间复杂度：，调用方法需要常量的空间。