LeetCode 575. 分糖果

Categories:

题目描述
思路分析
1. 解法一：去重计数（推荐）
相似题目

题目描述

✅ 575. 分糖果

思路分析

解法一：去重计数（推荐）

核心思路：

共有 n 颗糖，妹妹最多拿 n/2 颗。

去重后糖果种类数为 distinct。

能得到的最大种类数为 min(distinct, n/2)。

复杂度分析：

时间复杂度：O(n)，其中 n 表示糖果数量。

空间复杂度：O(n)，用于集合去重。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        for (int t : candyType) {
            set.add(t);
        }

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

func distributeCandies(candyType []int) int {
	set := make(map[int]struct{})
	for _, v := range candyType {
		set[v] = struct{}{}
	}

	limit := len(candyType) / 2
	if len(set) < limit {
		return len(set)
	}
	return limit
}

相似题目

题目	难度	考察点
349. 两个数组的交集	简单	集合
217. 存在重复元素	简单	哈希表
645. 错误的集合	简单	计数
771. 宝石与石头	简单	计数
1748. 唯一元素的和	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/20091563