题解 | #组合数第k小#

题意整理

在所有组合数中，找到第k小的，并返回其值。

方法一（小顶堆）

1.解题思路

枚举从k个数中取若干个数的所有组合数，然后依次添加到堆，如果已经在堆，则不再添加。然后从堆里弹出k-1个数，此时的堆顶元素一定是第k小的组合数，直接返回。
由于数据量大，运行超时。

动图展示：
图片说明

2.代码实现

import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 
     * @param k int整型 
     * @return int整型
     */
    //大数常量1
    final BigInteger ONE=new BigInteger("1");

    public int kthSamllest (int k) {
        //特殊情况判断
        if(k==1) return 1;
        //用于去重
        Set<BigInteger> set=new HashSet<>();
        //初始化小顶堆
        PriorityQueue<BigInteger> queue=new PriorityQueue<>();
        //枚举所有组合数
        for(int i=1;i<=k;i++){
            for(int j=1;j<=i;j++){
                //如果第一次出现，则添加到堆
                if(!set.contains(C(i,j))){
                    set.add(C(i,j));
                    queue.offer(C(i,j));
                }
            }
        }

        //弹出k-1个元素
        for(int i=0;i<k-1;i++){
            queue.poll();
        }

        return queue.peek().intValue();
    }

    //计算大数组合
    private BigInteger C(int n,int m){
        return factorial(n).divide(factorial(m).multiply(factorial(n-m)));
    }

    //计算大数阶乘
    private BigInteger factorial(int n){
        BigInteger res=ONE;
        for(int i=2;i<=n;i++){
            BigInteger I=new BigInteger(String.valueOf(i));
            res=res.multiply(I);
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：计算一次组合数的时间复杂度是 $O(k)$ ，需要计算 $k*(k-1)/2$ 次，所以时间复杂度为 $O(k^3)$ 。
空间复杂度：需要额外大小为 $k*(k-1)/2$ 的小顶堆和set，所以空间复杂度为 $O(k^2)$ 。

方法二（数学）

1.解题思路

由于从每个数中取1的组合数是它本身，即 $C_k^{1}=k$ ，所以从1到k都是组合数，并且是连续的，从而，第k小的组合数一定是k。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param k int整型 
     * @return int整型
     */
    public int kthSamllest (int k) {
        //第1个到第k个组合数是从1开始的连续的自然数
        return k;
    }
}

3.复杂度分析

时间复杂度：直接返回k，所以时间复杂度为 $O(1)$ 。
空间复杂度：不需要额外的空间，所以空间复杂度为 $O(1)$ 。