LeetCode.575.Distribute Candies 分糖果

题目描述

575 Distribute Candies
https://leetcode-cn.com/problems/distribute-candies/
https://leetcode.com/problems/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 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:

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].

---

解题过程

这道题题意还是需要仔细阅读，有些绕。
抽象出来就是一个长度为2n的整数数组，从中选出n个数，要求这n个数尽可能互不相同(种类尽量多)，求n中互不相同的数的个数（或者说n中去重后的元素个数）
一下子就想到用哈希表，也就是Map映射，顺序遍历，依次入Map，key是数值，value随意，最后计算Map中元素个数与n比较取较小者。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int distributeCandies(int[] candies) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<candies.length; i++){
            map.put(candies[i], i);
        }
        if(map.size() >= candies.length/2){
            return candies.length/2;
        }else {
            return map.size();
        }
    }
}

public class DistributeCandies {
    public static void main(String[] args){
        Solution solution = new Solution();
        int[] candies = {1,1,1,1,2,2,2,3,3,3};
        System.out.println(solution.distributeCandies(candies));
    }
}

提交后看Discuss，才意识到用集合是更好的，不需要用Map，因为我们并不关心Key对应的Value值是什么。
下面的代码很简洁很漂亮：

public class Solution {
    public int distributeCandies(int[] candies) {
        Set<Integer> kinds = new HashSet<>();
        for (int candy : candies) kinds.add(candy);
        return kinds.size() >= candies.length / 2 ? candies.length / 2 : kinds.size();
    }
}

还有人给出了Java8的一行代码版，又使用了Stream

public class Solution {
    public int distributeCandies(int[] candies) {
        return Math.min(candies.length / 2, IntStream.of(candies).boxed().collect(Collectors.toSet()).size());
    }
}

提交的代码中速度最快的是用数组下标做Map的，这种是我觉得最巧妙的，就是空间复杂度略高。

public int distributeCandies(int[] candies) {
    int[] b = new int[200001];
    int nonEmptyBucketNo = 0;
    for (int i : candies)
        if (b[i + 100000]++ == 0)
            nonEmptyBucketNo++;
    return nonEmptyBucketNo <= candies.length / 2 ? nonEmptyBucketNo : candies.length / 2;
}

---

GitHub代码

algorithms/leetcode/leetcode/_575_DistributeCandies.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_575_DistributeCandies.java

---