10/7 每日一題(檢查是否可以分成相同數量的分組且每組的元素一致)

You are given an integer array deck where deck[i] represents the number written on the ith card.

Partition the cards into one or more groups such that:

• Each group has exactly x cards where x > 1, and
• All the cards in one group have the same integer written on them.

Return true if such partition is possible, or false otherwise.

 

Example 1:

Input: deck = [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].

Example 2:

Input: deck = [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

 

Constraints:

• 1 <= deck.length <= 104
• 0 <= deck[i] < 104

class Solution:

    def hasGroupsSizeX(self, deck: List[int]) -> bool:

        #分組條件必須拆成依樣數量的分組 , 且分組卡必須一致

        if len(deck)<2:

            return False

        nums=Counter(deck)

        #是否存在最大公因數

        val_list=list(nums.values())

        print(f'最大={max(val_list)}, 最小={min(val_list)}')

        if max(val_list) == min(val_list):

            return True

        min_ele=min(val_list)

        x=2

        #從2開始因為x>1

       

        n=len(val_list)

        while x <= min_ele:

            c=0

            for i in val_list:

                if i%x !=0:

                    c=0

                    break

                else:

                    c+=1

                    '檢查是否都通過'

            if c==n:

                return True

            x += 1

        return False

-------------------------直接使用math.gcd 回傳最大公因數

import math

class Solution:

    def hasGroupsSizeX(self, deck: List[int]) -> bool:

        #分組條件必須拆成依樣數量的分組 , 且分組卡必須一致

        if len(deck)<2:

            return False

        nums=Counter(deck)

        #是否存在最大公因數

        val_list=list(nums.values())

        val_list.sort()        

        gcd_ele=val_list[0]

        for i in val_list:

            gcd_ele=math.gcd(gcd_ele,i)

        return gcd_ele >1