leetcode （Distribute Candies）

Title：Distribute Candies    575

Difficulty：Easy

原題leetcode位址: https://leetcode.com/problems/distribute-candies/

1.  采用set儲存糖果種類

時間複雜度：O(n)，一次一層循環。

空間複雜度：O(n)，申請Set。

/**
     * 采用set集合儲存糖果的類型
     * @param candies
     * @return
     */
    public static int distributeCandies(int[] candies) {

        Set<Integer> set = new HashSet<>();

        for (int candy : candies) {
            if (!set.contains(candy)) {
                set.add(candy);
            }
        }

        return Math.min(set.size(), candies.length / 2);

    }
           

2.  采用排序計算糖果種類

時間複雜度：O(n)，一次一層循環。

空間複雜度：O(n)，申請Set。

/**
     * 先将candies排序，算出種類
     * @param candies
     * @return
     */
    public static int distributeCandies2(int[] candies) {

        Arrays.sort(candies);
        int count = 1;

        for (int i = 1; i < candies.length; i++) {
            if (candies[i] != candies[i - 1]) {
                count++;
            }
        }

        return Math.min(count, candies.length / 2);

    }