题解 | #牛牛找子集#

题意整理

• 给定n个数，现在要将这n个数分成k个子集，使得相同子集的数量尽可能多。
• 求满足条件的子集（如果有多个，输出字典序最小的那个）。

方法一（暴力）

1.解题思路

• 首先统计数组中所有元素出现次数，记录在map数组。
• 然后确定满足条件的相同子集的个数，最小值显然为1，最大值为，因为最多分成个相同的子集。
• 线性查找满足条件的最大的子集个数，check的规则是分配次数大于等于k。分配的标准是：如果某个元素至少能被每个子集分1次，则可以分配。
• 根据找到的最大子集个数，还原对应的子集。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回找到能够满足游戏胜利条件的子集，如果有多个子集满足条件，返回字典序最小的即可。
     * @param n int整型 代表数字的数量
     * @param k int整型 代表子集的大小
     * @param s int整型一维数组 代表数字数组
     * @return int整型一维数组
     */
    //子集里元素个数
    int k;
    //计数数组
    int[] map;
    public int[] findSubset (int n, int k, int[] s) {
        //初始化
        this.k=k;
        map=new int[100010];
        for(int i=0;i<n;i++){
            map[s[i]]++;
        }

        //确定左右边界
        int l=1;
        int r=n/k;
        //线性查找
        int num=search(l,r);

        int[] res=new int[k];
        int id=0;
        for(int i=1;i<=100000;i++){
            if(map[i]/num>=1){
                //只要map[i]/num大于等于1，说明可以被分配到子集
                for(int j=0;j<map[i]/num;j++){
                    res[id++]=i;
                    if(id==k){
                        return res;
                    }
                }
            }
        }
        return null;
    }

    //x表示分成相同子集的个数
    private boolean check(int x){
        int cnt=0;
        for(int i=1;i<=100000;i++){
            //说明某个元素至少能被每个子集分1次
            if(map[i]/x>=1){
                //累加上分配次数
                cnt+=map[i]/x;
            }
            if(cnt>=k){
                return true;
            }
        }
        return false;
    }

    //如果满足check函数，则直接返回当前对应的下标
    private int search(int l,int r){
        for(int i=r;i>=l;i--){
            if(check(i)){
                return i;
            }
        }
        return l;
    }
}

3.复杂度分析

• 时间复杂度：假设数组中不同元素的总数目为count，check函数最多检查count次，线性查找最多执行次check函数，还原子集的时候，循环体最多执行次，所以时间复杂度是。
• 空间复杂度：需要额外大小为count的map数组，所以空间复杂度为。

方法二（二分查找）

1.解题思路

• 首先统计数组中所有元素出现次数，记录在map数组。
• 然后确定二分查找的左右边界，左边界显然为1，右边界为。
• 二分查找可行域的右边界，也就是分成相同子集的最大个数。
• 根据找到的最大子集个数，还原对应的子集。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回找到能够满足游戏胜利条件的子集，如果有多个子集满足条件，返回字典序最小的即可。
     * @param n int整型 代表数字的数量
     * @param k int整型 代表子集的大小
     * @param s int整型一维数组 代表数字数组
     * @return int整型一维数组
     */
    //子集里元素个数
    int k;
    //计数数组
    int[] map;
    public int[] findSubset (int n, int k, int[] s) {
        //初始化
        this.k=k;
        map=new int[100010];
        for(int i=0;i<n;i++){
            map[s[i]]++;
        }

        //确定左右边界
        int l=1;
        int r=n/k;
        //二分查找
        int num=binarySearch(l,r);

        int[] res=new int[k];
        int id=0;
        for(int i=1;i<=100000;i++){
            if(map[i]/num>=1){
                //只要map[i]/num大于等于1，说明可以被分配到子集
                for(int j=0;j<map[i]/num;j++){
                    res[id++]=i;
                    if(id==k){
                        return res;
                    }
                }
            }
        }
        return null;
    }

    //x表示分成相同子集的个数
    private boolean check(int x){
        int cnt=0;
        for(int i=1;i<=100000;i++){
            //说明某个元素至少能被每个子集分1次
            if(map[i]/x>=1){
                //累加上分配次数
                cnt+=map[i]/x;
            }
            if(cnt>=k){
                return true;
            }
        }
        return false;
    }

    //二分查找可行域的右边界，也就是分成相同子集的最大个数
    private int binarySearch(int l,int r){
        while(l<r){
            //上取整，防止死循环
            int mid=l+(r-l+1)/2;
            //如果满足check函数，则排除左边所有元素，保留当前元素
            if(check(mid)){
                l=mid;
            }
            //如果不满足check函数，则排除右边所有元素
            else{
                r=mid-1;
            }
        }
        return l;
    }
}

3.复杂度分析

• 时间复杂度：假设数组中不同元素的总数目为count，check函数最多检查count次，二分查找最多执行次check函数，还原子集的时候，循环体最多执行次，所以时间复杂度是。
• 空间复杂度：需要额外大小为count的map数组，所以空间复杂度为。