LeetCode575 Distribute Candies

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Note:

  1. The length of the given array is in range [2, 10,000], and will be even.
  2. The number in given array is in range [-100,000, 100,000].

样例

1
2
3
4
5
6
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies.
1
2
3
4
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies.

思路

有偶数个不同种类的糖果,将其平均分给两个人,问某人能够得到最多的种类数是多少

首先,用哈希表记录种类数,这是答案的上限,而一个人只能获得一半的糖果,所以这又是一个上限。

最终的答案为二者取最小值。

代码

1
2
3
4
5
6
7
8
class Solution {
public:
int distributeCandies(vector<int>& candies) {
unordered_map<int, int> count;
for(int x: candies) count[x]++;
return min(count.size(), candies.size() / 2);
}
};
分享到 评论