本來(lái)有想到用找公約數(shù)的方法來(lái)替代循環(huán)求余找到分組的數(shù)量窃躲，現(xiàn)在仔細(xì)一想刑巧，其實(shí)完全可以直接用求公約數(shù)的方法找到正確答案烤镐。
解析：
舉例數(shù)組：[1,1,1,1,2,2,3,3,3,3]乍构，1的數(shù)量是4绰精，3的數(shù)量是4,2的數(shù)量是2哑诊。劃分為四人一組2就不滿足要求群扶，但通過(guò)求4與2的公約數(shù)，可以得出2镀裤，劃分為兩人一組即可滿足條件竞阐。故可以用計(jì)數(shù)的方法犧牲空間來(lái)提高執(zhí)行時(shí)間。
缺點(diǎn)：
計(jì)數(shù)的方法在數(shù)據(jù)間隔很大的時(shí)候需要浪費(fèi)很多空間暑劝，如[1,1,10000,10000]骆莹，如果使用count計(jì)數(shù)，中間9998位是被浪費(fèi)掉的担猛。當(dāng)然效率也會(huì)比較高幕垦。
排除掉的做法：
image.png
本來(lái)打算給計(jì)數(shù)排個(gè)序丢氢，然后從有數(shù)據(jù)的位置數(shù)起來(lái)，遇見(jiàn)0就停止循環(huán)先改，減少運(yùn)行次數(shù)疚察，沒(méi)想到提交后發(fā)現(xiàn)排序后花的時(shí)間更多了。
image.png
不排序的結(jié)果如下：
image.png
內(nèi)存消耗和第一個(gè)版本差不多仇奶，但是速度是兩倍貌嫡。
image.png
理論上第二個(gè)解法應(yīng)該會(huì)消耗更多的內(nèi)存，可能是因?yàn)闇y(cè)試數(shù)據(jù)間隔不大的緣故该溯，所以計(jì)數(shù)的缺點(diǎn)沒(méi)有體現(xiàn)出來(lái)岛抄。
代碼如下：
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
bool hasGroupsSizeX(vector<int>& deck)
{
int people_number=0;
int count[10000] = {0};
int n = deck.size();
if (n == 1) return false;
for (int i = 0;i < n;i++)
count[deck[i]]++;
for (int i = 0;i < n;i++)
{
if (count[i] > 0)
{
people_number = gcd(people_number, count[i]);
if (people_number == 1)
return false;
}
}
return true;
}
