575 Distribute Candies 分糖果
Description:
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.
Example:
Example 1:
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.
Example 2:
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.
Note:
The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].
題目描述:
給定一個(gè)偶數(shù)長(zhǎng)度的數(shù)組，其中不同的數(shù)字代表著不同種類的糖果，每一個(gè)數(shù)字代表一個(gè)糖果县袱。你需要把這些糖果平均分給一個(gè)弟弟和一個(gè)妹妹嫉戚。返回妹妹可以獲得的最大糖果的種類數(shù)洛退。
示例 :
示例 1:
輸入: candies = [1,1,2,2,3,3]
輸出: 3
解析: 一共有三種種類的糖果块蚌，每一種都有兩個(gè)传轰。
最優(yōu)分配方案：妹妹獲得[1,2,3],弟弟也獲得[1,2,3]背传。這樣使妹妹獲得糖果的種類數(shù)最多呆瞻。
示例 2 :
輸入: candies = [1,1,2,3]
輸出: 2
解析: 妹妹獲得糖果[2,3],弟弟獲得糖果[1,1]，妹妹有兩種不同的糖果径玖，弟弟只有一種痴脾。這樣使得妹妹可以獲得的糖果種類數(shù)最多。
注意:
數(shù)組的長(zhǎng)度為[2, 10,000]梳星，并且確定為偶數(shù)赞赖。
數(shù)組中數(shù)字的大小在范圍[-100,000, 100,000]內(nèi)滚朵。
思路:
題意可以轉(zhuǎn)化為求數(shù)組中的不同元素的個(gè)數(shù), 轉(zhuǎn)換為 set, 如果不同的元素個(gè)數(shù)大于 size / 2就直接返回 size / 2, 否則返回不同元素的個(gè)數(shù)
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
int distributeCandies(vector<int>& candies)
{
bitset<200001> b;
for (int candy : candies) b.set(candy + 100000);
return min(b.count(), candies.size() / 2);
}
};
Java:
class Solution {
public int distributeCandies(int[] candies) {
BitSet b = new BitSet(200001);
for (int candy : candies) b.set(candy + 100000);
return Math.min(b.cardinality(), candies.length / 2);
}
}
Python:
class Solution:
def distributeCandies(self, candies: List[int]) -> int:
return len(set(candies)) if len(set(candies)) < len(candies) // 2 else len(candies) // 2
