题意

一个 元集合（允许元素相同），要找一个 元子集，使得能在原集合中选出尽可能多的该集合。
多种方案输出字典序最小的。

解法1：枚举答案（本该TLE却没有）

可以考虑枚举相同子集的数目。（范围在 ）
对于每个待验证的答案，统计各相同元素最多分别能在每个子集中放几个。若它们的和不小于 则为合法方案。
若最后个数多于 ，去掉大的部分

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回找到能够满足游戏胜利条件的子集，如果有多个子集满足条件，返回字典序最小的即可。
     * @param n int整型 代表数字的数量
     * @param k int整型 代表子集的大小
     * @param s int整型vector 代表数字数组
     * @return int整型vector
     */
    vector<int> findSubset(int n, int k, vector<int>& s) {
        // write code here
        vector<int>c(1000001);
        for(auto x: s) ++c[x]; // 统计相同元素
        int r;
        for(int i=n/k; i>=1; --i){ // 枚举答案
            int cnt=0;
            for(auto x:c) cnt+=x/i;  // 贪心选取元素
            if(cnt>=k) { // 合法
                r=i;
                break;
            }
        }
        vector<int> ret;
        for(int x=1; x<=100001; ++x){
            for(int i=1; i<=c[x]/r; ++i) ret.push_back(x);
        }
        while(ret.size()>k) ret.pop_back(); // 去掉多的
        return ret;
    }
};

复杂度分析

空间复杂度: 需要统计相同元素的个数，
时间复杂度：对每个数目，都需要扫一遍所有元素进行统计，

解法2：二分答案

可以考虑二分相同子集的数目。（范围在 ）
对于每个待验证的答案，统计各相同元素最多分别能在每个子集中放几个。若它们的和达到 则为合法方案。
二分时，如果不能得到合法方案，证明数目偏大，反之可能偏小。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回找到能够满足游戏胜利条件的子集，如果有多个子集满足条件，返回字典序最小的即可。
     * @param n int整型 代表数字的数量
     * @param k int整型 代表子集的大小
     * @param s int整型vector 代表数字数组
     * @return int整型vector
     */
    vector<int> findSubset(int n, int k, vector<int>& s) {
        // write code here
        vector<int>c(1000001);
        for(auto x: s) ++c[x];
        int l=1, r=n/k;
        while(l<r){
            int mid=(l+r+1)/2; // 二分答案
            int cnt=0;
            for(auto x:c) cnt+=x/mid;
            if(cnt<k) r=mid-1;
            else l=mid;
        }
        vector<int> ret;
        for(int x=1; x<=100001; ++x){
            for(int i=1; i<=c[x]/r; ++i) ret.push_back(x);
        }
        while(ret.size()>k) ret.pop_back(); // 去掉多的
        return ret;
    }
};

复杂度分析

空间复杂度：需要统计相同元素的个数，
时间复杂度：对每个数目，都需要扫一遍所有元素进行统计。有 个数待验证，