专栏首页五分钟学算法三分钟看完「分糖果」算法问题

三分钟看完「分糖果」算法问题

题目描述

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

示例 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],妹妹有两种不同的糖果,弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

注意:

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

题目解析

总共有 n 个糖,平均分给两个人,每人得到 n/2 块糖,那么能拿到的最大的糖的种类数也就是 n/2 种,不可能更多,只可能更少。

所以只需要统计出糖的种类数,如果糖的种类数小于 n/2,说明拿不到 n/2种糖,最多能拿到的种类数就是当前糖的总种类数。最后,看(数量的一半)和(所有的种类)哪个先达到,取两者中较小的值即可。

举个例子:

  • 极端情况1:所有糖都不重样,这种情况妹妹也只能拿到一半的糖果。
  • 极端情况2:只有一种糖,这种情况妹妹只能得到一种糖果。
  • 平均情况:每个糖都有两个,这种情况妹妹可以拿到所有种类,数量与 极端情况1 一样。

求糖果的种类数使用 hash 即可。

图片描述

代码实现

class Solution {
    public int distributeCandies(int[] candies) {
        Set<Integer> nums = new HashSet<>();
        for (int i = 0; i < candies.length; i++) {
            nums.add(candies[i]);
        }
        int numNums = nums.size();
        int numTarget = candies.length / 2;
        return numNums >= numTarget ? numTarget : numNums;
    }
}

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 几道和散列(哈希)表有关的面试题

    散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到...

    五分钟学算法
  • 一起刷题学习 Git/SQL/正则表达式

    虽说我没事就喜欢喷应试教育,但我也从应试教育中发现了一个窍门:如果能够以刷题的形式学习某项技能,效率和效果是最佳的。

    五分钟学算法
  • 每天一算: Number of Boomerangs

    五分钟学算法
  • 每日一题(7)

    考点:自增自减运算符 你是不是一看到就喊"100",真的这么简单么 其实没这么简单

    KEN DO EVERTHING
  • Android 移动直播(LiteAV)直播播放如何获取YUV数据

    开发者因为场景需要,希望能获取到视频画面的原始数据(YUV 数据),然后再进行处理或渲染。

    腾讯云-yyuanchen
  • IIT 坎普尔咨询集团:将机器学习和管理咨询的方法应用到社会公益中(CS)

    IIT坎普尔咨询集团(IIT Kanpur Consulting Group)是印度的先驱研究机构之一,他们致力于研究机器学习和策略咨询在社会公益中的应用。该集...

    Pamela_Lin
  • 动态规划-数正方形(详解)

    描述: 晓萌有一个N×N的的棋盘,中间有N*N个正方形的1×1的格子,他随机在棋盘上撒上一些棋子(假设全部正好落在各个格子里)。他希望知道,当前的棋盘上有多少个...

    张诺谦
  • C#随机不重复给数组赋值1-100并排…

    IArray[i] = Convert.ToInt32(arraylist[iKey]);

    Dabelv
  • 575. 分糖果

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

    lucifer210
  • 符合NIS指令的网络安全成熟度评估框架(CS CR)

    NIS指令规定了主要的服务运营商和数字服务提供商的网络和信息系统的安全义务,并要求国家主管当局评估其遵守这些义务的情况。本文描述了一种新的网络安全成熟度评估框架...

    Elva

扫码关注云+社区

领取腾讯云代金券