Distribute Candies–LeetCode#575

575.Distribute Candies

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Example 1:

Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies.

Example 2:

Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies.
Note:

  1. The length of the given array is in range [2, 10,000], and will be even.
  2. The number in given array is in range [-100,000, 100,000].
 思路:一个整形数组平均分成两份,求分出来的不同值有多少。就是求数组中整数不同的有几种与平均分后每组分到多少个的比较,返回比较下来小的值。
代码如下:
import java.util.Arrays;
/**
 * Created by Poldi on 2017/7/7.
 */
public class DistributeCandies {
    public int distributeCandies(int[] candies) {
        int num = candies.length/2;
        int different = 1;
        Arrays.sort(candies);
        for (int i=0;i<candies.length-1;i++){
            if (candies[i]!=candies[i+1]){
                different++;
            }
        }
        System.out.println(different);
        if (different>num){
            return num;
        }else if (different<num){
            return different;
        }else {
            return num;
        }
    }
    public static void main(String[] args) {
        DistributeCandies distributeCandies=new DistributeCandies();
        int[] ints={100000,0,100000,0,100000,0,100000,0,100000,0,100000,0};
        System.out.println(distributeCandies.distributeCandies(ints));
    }
}

另外有种更简便的思路,使用Set能直接把原数组中重复的整数去除,Set的实现类的集合对象中不能够有重复元素,HashSet也一样他是使用了一种标识来确定元素的不重复,HashSet用一种算法来保证HashSet中的元素是不重复的。从而可获取不同整数的个数,与平均分后的数量比较。
代码如下:

public int distributeCandies(int[] candies) {
    int num = candies.length/2;
    Set<Integer> candy = new HashSet<>();
    for (int i=0;i<candies.length;i++){
        candy.add(candies[i]);
    }
    if (candy.size()>num){
        return num;
    }else if (candy.size()<num){
        return candy.size();
    }else {
        return num;
    }
}

 

文章已创建 110

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部