亚麻SDE1题：无重复建组

There are N countries, each country has countries players. You need to form teams of size K such that each player in the team is from a different country.

Given N and number of players from each country and size K.  Find the maximum number of teams you can form.

1. public int getMinTeams(int[] countries, int K)

复制代码

这题是不是O（N）可以做出来？

可不可以这么做，想象有k个宽为1的桶，每个国家的运动员数量S代表一个高为S，宽为1的bar， 那么就是把这些 bar尽量均匀的分到k个桶里，最后桶里的bar的最低总高度就是队伍数量。

但是有一个问题是怎样O(N)的 最均匀的分配bar到k个桶里

我当时的思路是这样：
AAAAA
BBBBBBB
CCCCC
K=4
总共有5+7+5=17个。17/4 需要 5个桶。可是最长的B需要7个桶。因此答案是这两个里面的最大的。7个桶。

14417335 发表于 2019-2-18 05:08
我当时的思路是这样：
AAAAA
BBBBBBB

不对。EACH TEAM MEMBER 要从不同国家来，K=4的话应该是0.因为没有四个人是不同国家。

albertguosgp 发表于 2019-2-18 05:14
不对。EACH TEAM MEMBER 要从不同国家来，K=4的话应该是0.因为没有四个人是不同国家。

你提示的对！题目的意思是可以有人进不去组但是组必须K个不同国家的人。照我的理解那么做的话是无人漏下但是组不满。
看来需要 N*log(C)

14417335 发表于 2019-2-18 05:33
你提示的对！题目的意思是可以有人进不去组但是组必须K个不同国家的人。照我的理解那么做的话是无人漏下 ...

O(N)能做出来。有空我写写贴上来。

感觉用priority queue做，放入国家和人数的对象，每次从中取最大的那个，加上visited，可以用set判断去重。复杂度是NlogN？

eggface 发表于 2019-2-21 05:32
感觉用priority queue做，放入国家和人数的对象，每次从中取最大的那个，加上visited，可以用set判断去重。 ...

我想的是避免使用visited。每次组队的时候，拿出来k个。最后一起全部放回去。这样保证了入选的一定是不同队的也就避免了visited。

还没想好有无优化的可能。O（N）不知道能不能做。也许albertguosgp可以带来惊喜。