【問題描述】

給定一副牌，每張牌上都寫著一個整數(shù)。此時(shí)，你需要選定一個數(shù)字 X，使我們可以將整副牌按下述規(guī)則分成 1 組或更多組：每組都有?X?張牌。 組內(nèi)所有的牌上都寫著相同的整數(shù)。 僅當(dāng)你可選的 X >= 2 時(shí)返回?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

【解答思路】

1. 時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(N)

• 遍歷一次，統(tǒng)計(jì)每個數(shù)值的個數(shù)，如果某個數(shù)值只有 1 個，直接返回 false；
• 輸入 [2, 2, 2, 2, 3, 3, 3, 3, 3, 3]，其實(shí)也是符合題意的分組，2 有 4個，3 有 6 個，相同的 2 和 3 都需要拆成 2 個一組，即需要求兩兩元素個數(shù)的公約數(shù)是否有共同的公約數(shù)。

public boolean hasGroupsSizeX(int[] deck) {//計(jì)數(shù) int[] cnt = new int[10000];for(int x: deck){cnt[x]++; }//避免虛幻內(nèi)賦值int a= cnt[0];for(int i: cnt){//出現(xiàn)單個返回錯誤if(i==1){return false;}if(i>1){//循環(huán)計(jì)算最大公約數(shù)a = gcd(a,i);if(a ==1 ){return false;}}}return true;}/*最大公約數(shù)12 ? 9 = 1 ...... 39 ? 3 = 3 ...... 03返回 0跳出循環(huán)*/public int gcd(int x, int y){int max = Math.max(x,y);int min = Math.min(x,y);while(min!= 0){int temp =min;min = max% min;max = temp;}return max;/* //遞歸求最大公約數(shù)（偉哥提供） private int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}} 作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/solution/qiu-jie-zui-da-gong-yue-shu-java-by-liweiwei1419/

?###### 2. 甜姨的精簡操作
2.1 3ms的刀法

class Solution {public boolean hasGroupsSizeX(int[] deck) {// 計(jì)數(shù)int[] counter = new int[10000];for (int num: deck) {counter[num]++;}// 迭代求多個數(shù)的最大公約數(shù)int x = 0;for(int cnt: counter) {if (cnt > 0) {x = gcd(x, cnt); if (x == 1) { // 如果某步中g(shù)cd是1，直接返回falsereturn false;}}}return x >= 2;}// 輾轉(zhuǎn)相除法private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);} }作者：sweetiee 鏈接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/solution/3ms-jian-dan-java-fu-zeng-reducexie-fa-miao-dong-b/

2.2 迭代求gcd的過程可以用reduce算子進(jìn)行代碼簡化

class Solution {public boolean hasGroupsSizeX(int[] deck) {// 計(jì)數(shù)int[] counter = new int[10000];for (int num: deck) {counter[num]++;}// reduce求多個數(shù)的最大公約數(shù)// （因?yàn)檫@里當(dāng)gcd==1的時(shí)候沒有提前終止，并且本題數(shù)據(jù)量太小無法用并行流，因此耗時(shí)10ms，比for循環(huán)慢點(diǎn)）return Arrays.stream(counter).reduce(this::gcd).getAsInt() >= 2;}// 輾轉(zhuǎn)相除法private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);} }作者：sweetiee 鏈接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/solution/3ms-jian-dan-java-fu-zeng-reducexie-fa-miao-dong-b/

其中，reduce(this::gcd) 即為 reduce((a, b) -> gcd(a, b))
下圖以reduce((a, b) -> a + b)來解釋reduce算子：

【總結(jié)】

1.求最大公約數(shù)（輾轉(zhuǎn)相除法）

public int gcd(int x, int y){int max = Math.max(x,y);int min = Math.min(x,y);while(min!= 0){int temp =min;min = max% min;max = temp;}return max; private int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);} private int gcd (int a, int b) {return b == 0? a: gcd(b, a % b);

統(tǒng)計(jì)個數(shù)的時(shí)候，可以使用哈希表，也可以使用數(shù)組。

• 看題目中的數(shù)據(jù)范圍，如果題目中說，輸入數(shù)據(jù)只包含小寫字母（大寫字符）使用數(shù)組統(tǒng)計(jì)是相對方便的
• 哈希表底層也是數(shù)組。使用數(shù)組做計(jì)數(shù)任務(wù)其實(shí)是自己編寫了哈希函數(shù)

變量名稱只有少數(shù)幾個詞可以寫縮寫用，一般情況下，都用全稱。

• cnt 表示 count， res 表示 result ，ans 表示 answer

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第914题][最大公约数]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。