思路:举例推演即可得以下结论: 假设数组长度为n,不同数字种类数为k, 1.若k < n/2 ,则sister最多拿到k种数. 2.若k > n/2,则由于sister和brother要相等的限制,sister最多也只能拿到n/2. 结论:sister最多拿到min(k, n/2)种.
用集合set即可统计不同数字的种类,考虑到无序集合unordered_set效率更高,速度更快.
//cpp
class Solution {
public:
int distributeCandies(vector<int>& candies) {
unordered_set<int> hash;
for (int i = 0; i < candies.size(); i++) {
hash.insert(candies[i]);
}
return min(hash.size(), candies.size()/2);
}
};
#py
class Solution:
def distributeCandies(self, candies: List[int]) -> int:
n = len(candies)
k = len(set(candies))
return min(k, n//2)
