Problem
n a deck of cards, each card has an integer written on it.
Return true
if and only if you can choose X >= 2
such that it is possible to split the entire deck into 1 or more groups of cards, where:
- Each group has exactly
X
cards. - All the cards in each group have the same integer.
Example 1:
Input: [1,2,3,4,4,3,2,1] Output: true Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]
Example 2:
Input: [1,1,1,2,2,2,3,3] Output: false Explanation: No possible partition.
Example 3:
Input: [1] Output: false Explanation: No possible partition.
Example 4:
Input: [1,1] Output: true Explanation: Possible partition [1,1]
Example 5:
Input: [1,1,2,2,2,2] Output: true Explanation: Possible partition [1,1],[2,2],[2,2]
Note:
1 <= deck.length <= 10000
0 <= deck[i] < 10000
Solution 1: HashTable + Brute Force
Try all possible Xs. 2 ~ deck.size()
Time complexity: ~O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, 16 ms class Solution { public: bool hasGroupsSizeX(vector<int>& deck) { unordered_map<int, int> counts; for (int card : deck) ++counts[card]; for (int i = 2; i <= deck.size(); ++i) { if (deck.size() % i) continue; bool ok = true; for (const auto& pair : counts) if (pair.second % i) { ok = false; break; } if (ok) return true; } return false; } }; |
Solution 2: HashTable + GCD
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua, 16 ms class Solution { public: bool hasGroupsSizeX(vector<int>& deck) { unordered_map<int, int> counts; for (int card : deck) ++counts[card]; int X = deck.size(); for (const auto& p : counts) X = __gcd(X, p.second); return X >= 2; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Somebody class Solution { public boolean hasGroupsSizeX(int[] deck) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i=0; i<deck.length; i++) { int curr = deck[i]; if (map.containsKey(curr)) { map.put(curr, map.get(curr) + 1); } else { map.put(curr, 1); } } // O(nLogn) int gcd = 0; for(Integer key: map.keySet()) { gcd = findGCDOfTwoNumbers(map.get(key), gcd); } return gcd >= 2; } // O(Log n) public static int findGCDOfTwoNumbers (int a, int b) { if (b == 0) { return a; } return findGCDOfTwoNumbers(b, a%b); } } |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment