leetcode 575. 分糖果

leetcode 575. 分糖果.

题目描述

575. 分糖果

Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。

医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。

给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。

示例 1：

输入：candyType = [1,1,2,2,3,3] 输出：3 解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。 示例 2：

输入：candyType = [1,1,2,3] 输出：2 解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。 示例 3：

输入：candyType = [6,6,6,6] 输出：1 解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。

提示：

n == candyType.length 2 <= n <= 104 n 是一个偶数 -105 <= candyType[i] <= 105

解题思路

法1

模拟排序法
将糖果进行排序,相同的糖果就会在一起,使用循环遍历的方法计算糖果的种类的数量即可,

如果数量>1/2总量则返回1/2总量

如果小于则返回种类的数量

• 时间复杂度(O(nlogn))
• 空间复杂度(O(1))

法2

哈希表\

建立一个map,key为种类(int),value为是否存在,(bool)

遍历数组,如果该int值在map在对应的值为false,就改为ture,出现过,最后统计map的长度

如果数量>1/2总量则返回1/2总量

如果小于则返回种类的数量

• 时间复杂度(O(n))
• 空间复杂度(O(n))

执行结果

法1

func distributeCandies(candyType []int)(r int) {
r=1
sort.Ints(candyType)
for i := 1; i < len(candyType)&&r<len(candyType)/2; i++ {
 if candyType[i] !=candyType[i-1]{
  r++
 }
}
return
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 180 ms , 在所有 Go 提交中击败了 14.69% 的用户 内存消耗： 7 MB , 在所有 Go 提交中击败了 92.66% 的用户 通过测试用例： 206 / 206

法2