題目：卡牌分組
給定一副牌，每張牌上都寫著一個整數，
此時，你需要選定一個數字 X，使我們可以將整副牌按下述規則分成 1 組或更多組：
每組都有 X 張牌，
組內所有的牌上都寫著相同的整數，
僅當你可選的 X >= 2 時回傳 true，
示例 1：
輸入：[1,2,3,4,4,3,2,1]
輸出：true
解釋：可行的分組是 [1,1]，[2,2]，[3,3]，[4,4]
示例 2：
輸入：[1,1,1,2,2,2,3,3]
輸出：false
解釋：沒有滿足要求的分組，
示例 3：
輸入：[1]
輸出：false
解釋：沒有滿足要求的分組，
示例 4：
輸入：[1,1]
輸出：true
解釋：可行的分組是 [1,1]
示例 5：
輸入：[1,1,2,2,2,2]
輸出：true
解釋：可行的分組是 [1,1]，[2,2]，[2,2]
提示：
1 <= deck.length <= 10000
0 <= deck[i] < 10000
思路：
首先根據題目條件，要求我們將牌分成一組或者多組，并且每組牌都是相同的，
我們可以想到，如果每組只有一張牌，那么無論有多少牌，都是有符合條件的分法的，
如果每組有兩張牌，那么每一種相同牌的總數量就必須是2的倍數，才有符合條件的分法，
如果每組有三張牌，那么每一張相同牌的總數量就必須是3的倍數，才有符合條件的分法，
由此類推，我們要找的數x則是：
★：設集合y
- 所有相同牌的總數都是 y 中元素的倍數，也就是都可以整除 y 中的元素
- x 則是 y 元素盡可能大的數
很明顯，y 集合則是所有相同牌數量的公約數，x 則是他們的最大公約數，
上代碼(c)：
//求最大公約數
int gcd( int x, int y ) { int tmp; while( y != 0 ) { tmp = x; x = y; y = tmp%y; } return x; } bool hasGroupsSizeX(int* deck, int deckSize){ int count[10005] = {0}; int x = -1; for( int i = 0; i < deckSize; i++ ) { count[deck[i]]++; } for( int i = 0; i < 10005; i++ ) { if( count[i] > 0 ) { if( x == -1 ) ans = count[i]; else x = gcd( ans, count[i] ); } } if( x >= 2 ) return true; return false; }
2020-03-27-19:03:11
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40818.html
標籤：C
上一篇：使用mutex同步多行程