575. 分糖果

本题来自LeetCode：575. 分糖果^[1]

题目描述

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
示例 1:

输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果，每一种都有两个。
     最优分配方案：妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

示例 2 :

输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1]，妹妹有两种不同的糖果，弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

注意:
数组的长度为[2, 10,000]，并且确定为偶数。
数组中数字的大小在范围[-100,000, 100,000]内。

题目分析

本题需要从两个方面来考虑：

若妹妹的拥有的糖已经等于总糖数的一半，那么剩下的糖都分配给弟弟。

若妹妹的拥有的糖已经小于总糖数的一半：

若某种糖，妹妹`没有`，那么优先分配给妹妹；

若某种糖，妹妹`有`，那么优先分配给弟弟；

题目解答

class Solution {
    public int distributeCandies(int[] candies) {
        // 妹妹获得的糖果种类
        SetInteger sisterKinds = new HashSet();
        // 弟弟获得的糖果数
        int brotherCandies = 0;
        // 半数糖果
        int half = candies.length  1;
        for(int i = 0; i  candies.length; i ++) {
            // 若妹妹的糖果数已经超过半数，剩下的糖都是弟弟的了
            if(i = half + brotherCandies) {
                break;
            }
            // 若弟弟的糖果数没有超过半数
            if(brotherCandies  half) {
                // 该种类的糖，妹妹已经拥有，则分配给弟弟
                if(sisterKinds.contains(candies[i])) {
                    brotherCandies ++;
                    continue;
                }
            }
            // 分配给妹妹
            sisterKinds.add(candies[i]);
        }
        return sisterKinds.size();
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(n)

参考资料

575. 分糖果: https://leetcode-cn.com/problems/distribute-candies

原文始发于微信公众号（xiaogan的技术博客）：