30分解法

用i遍历所有可能的答案(1-1e3),用j遍历n个数，每当a[j]%i==0时给答案i的权值++，最后从小到大扫一遍所有可能答案的权值，每遇到k的都更新ans=i即可，最后将ans返回，时间复杂度o(n^2),空间复杂度o(n);

100分做法

介绍两种做法，一种时间复杂度的，一种时间复杂度的

1.时间复杂度,空间复杂度的做法：

对于每个数，我们可以算它对所有因子的影响，只需要从$1到\sqrt{n}枚举因子即可，比较需要注意的是，对于平方数，它的开方因子贡献只有1，需要特判，代码如下：

int cnt[100005];
class Solution {
public:
    /**
     * 
     * @param arr int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int Maximumnumber(vector<int>& arr, int k) {
        // write code here
        int i,j,n=arr.size();
        for(i=0;i<n;i++)
        {
            for(j=1;j*j<arr[i];j++)
            {
                if(arr[i]%j==0)
                {
                    cnt[j]++;
                    cnt[arr[i]/j]++;
                }
            }
            if(j*j==arr[i])cnt[j]++;
        }
        int ans=1;
        for(int i=100000;i>=2;i--)
        {
            if(cnt[i]>=k){ans=i;break;}
        }
        return ans;
    }
};

2.时间复杂度,空间复杂度的做法：

可以先统计每个数的个数，然后对于每个数做为因子的贡献，是他所有倍数个数的和。一层循环遍历数的范围(1-1e5)，第二层循环遍历每个数，然后翻倍这个数，第二层循环的时间为1/n+2/n+...+n/n，是调和级数，在n足够大的情况下时间复杂度趋近logn，所以总的时间复杂度当然，本题数据范围较小，在两做法时间上几乎看不出差别，但如果数据范围到了1e6，经测试第一种做法大概需要9-10s，第二种做法只需要1s左右，还是有显著的时间优势的。代码如下：

int num[100005];
int cnt[100005];
class Solution {
public:
    /**
     *
     * @param arr int整型vector
     * @param k int整型
     * @return int整型
     */
    int Maximumnumber(vector<int>& arr, int k) {
        // write code here
        for(int i=0;i<arr.size();i++)num[arr[i]]++;
        for(int i=2;i<=1e5;i++)
        {
            for(int j=i;j<=1e5;j+=i)
            {
                cnt[i]+=num[j];
            }
        }
        int ans=1;
        for(int i=1e5;i>=2;i--)
        {
            if(cnt[i]>=k){ans=i;break;}
        }
        return ans;
    }
};