🚩传送门：https://leetcode-cn.com/problems/distribute-candies/

题目

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

示例 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. 生成代表糖果的给定 numsnums 数组的所有排列组合，并确定所生成数组前半部分中元素种类的数目。

    为确定数组前半部分中种类的数目，将所有前半部分的元素放在一个集合中，并计算集合中种类的数目。

  2. 计算前半部分中所有可能的排列组合的种类，并返回种类最大值。


复杂度分析

时间复杂度：

空间复杂度：，递归树的深度可以达到 。

官方代码

  1. public class Solution {
  2.     //1.用来记录最大种类数
  3.     int max_kind = 0;
  4.     //#计算最大种类数函数
  5.     public int distributeCandies(int[] nums) {
  6.         permute(nums, 0);
  7.         return max_kind;
  8.     }
  10.     public void permute(int[] nums, int l) {
  11.         //#到达递归最底层,暗示当前是一种完整排列方式
  12.         if (l == nums.length - 1) {
  13.             //2.哈希set用来判重
  14.             HashSet < Integer > set = new HashSet < > ();
  15.             //3.将前半部分放入集合
  16.             for (int i = 0; i < nums.length / 2; i++) {
  17.                 set.add(nums[i]);
  18.             }
  19.             //4.集合数代表前半部分的种类数
  20.             max_kind = Math.max(max_kind, set.size());
  21.         }
  22.         //#排列组合递归函数
  23.         for (int i = l; i < nums.length; i++) {
  24.             swap(nums, i, l);
  25.             permute(nums, l + 1);
  26.             swap(nums, i, l);
  27.         }
  28.     }
  29.     //#交换函数
  30.     public void swap(int[] nums, int x, int y) {
  31.         int temp = nums[x];
  32.         nums[x] = nums[y];
  33.         nums[y] = temp;
  34.     }
  35. }

解题思路：优化的暴力法

优化方法之前，首先我们需要观察一点。

  1. 女孩能得到的糖果种类的最大数量是 ，其中 是指糖果的数量。
  2. 如果总的糖果种类数低于 的话，为了使女孩得到的种类数最大，我们会将所有单个的糖果分配给女孩。
  3. 为了在给定的 数组中找到糖果的种类数。方法是遍历给定的 数组。每当我们遇到一个元素，比如 时，我们可以将所有与 相同的元素标记为无效，并将种类计数增加 。
  4. 最后 是提供给女孩的糖果种类数。要返回的值由：给出。
    • 并且当 超过 时，我们可以停止对给定 数组的遍历。

复杂度分析

时间复杂度：， 表示 数组的大小。

对于每一个新发现的元素，我们遍历 的所有元素。在最坏的情况下，我们对 的每个元素都这样做。

空间复杂度：

官方代码

  1. public class Solution {
  2.     public int distributeCandies(int[] candies) {
  3.         int count = 0;
  4.         //1.依次遍历至结尾,若种类数超过n/2终止
  5.         for (int i = 0; i < candies.length && count < candies.length / 2; i++) {
  6.             //#此元素有效
  7.             if (candies[i] != Integer.MIN_VALUE) {
  8.                 //2.种类数增加
  9.                 count++;
  10.                 //3.从后依次标记相同元素无效
  11.                 for (int j = i + 1; j < candies.length; j++) {
  12.                     //#Integer.MIN_VALUE 用于标记此数字无效
  13.                     if (candies[j] == candies[i])
  14.                         candies[j] = Integer.MIN_VALUE;
  15.                 }
  16.             }
  17.         }
  18.         return count;
  19.     }
  20. }

解题思路：排序

我们可以对给定的 数组进行排序，并通过比较排序数组的相邻元素来找出唯一的元素。对于找到的每个新元素（与前一个元素不同），我们需要更新 。最后，要返回的值由：给出，如前面的方法所述。

复杂度分析

时间复杂度：

其中 是数组的长度，需要排序数组的时间。

空间复杂度：或者。

空间复杂度取决于使用的排序算法，根据是否进行原地排序（即不使用额外的数组进行临时存储）。

官方代码

  1. public class Solution {
  2.     public int distributeCandies(int[] candies) {
  3.         //1.对数组排序
  4.         Arrays.sort(candies);
  5.         int count = 1;
  6.         //2.依次遍历至结尾,若种类数超过n/2终止
  7.         for (int i = 1; i < candies.length && count < candies.length / 2; i++)
  8.             //3.排序过后,当前元素大于前面说明不相等,种类数增加
  9.             if (candies[i] > candies[i - 1])
  10.                 count++;
  11.         return count;
  12.     }
  13. }

解题思路：集合set

找到唯一元素数量的另一种方法是遍历给定 数组的所有元素，并继续将元素放入集合中。通过集合的属性，它将只包含 唯一 的元素。最后，可以计算集合中元素的数量，例如 。返回值由：给出，如前面的方法所述。其中 是 数组的长度。

复杂度分析

时间复杂度：

整个 数组只遍历一次。这里， 是 数组的长度。

空间复杂度：。

在最坏的情况下， 的大小为 。

官方代码

  1. public class Solution {
  2.     public int distributeCandies(int[] candies) {
  3.         //1.HashSet用于存放元素
  4.         HashSet < Integer > set = new HashSet < > ();
  5.         //2.遍历数组,存入set
  6.         for (int candy: candies) {
  7.             set.add(candy);
  8.         }
  9.         //3.判断返回值
  10.         return Math.min(set.size(), candies.length / 2);
  11.     }
  12. }