DistributeCandies [source code]

public class DistributeCandies {
    public int distributeCandies(int[] candies) {
        int[] b = new int[200001];
        int nonEmptyBucketNo = 0;
        for (int i : candies) if (b[i + 100000]++ == 0) nonEmptyBucketNo++;
        return nonEmptyBucketNo <= candies.length / 2 ? nonEmptyBucketNo : candies.length / 2;
    }

    public static void main (String[] args) {
        DistributeCandies tester = new DistributeCandies();
        int[] input1 = {1,1,2,2,3,3};
        int[] input2 = {1,1,2,3};
        int[] input3 = {1,1,1,1,1,1,2,3};
        int[] input4 = {1,2,3,4,5,6};
        int[] input5 = {90001, 90002, 90003, 90004};
        int[] input6 = {-90001, -90002, -90003, -90004};
        System.out.println(tester.distributeCandies(input6));
    }
}

这个问题刚拿到的时候毫无头绪, 这个也是经验不足. 而且这里问题的表述其实是一个optimization的问题, 这种问题有时候就觉得无从下手, 总不能用 search 来做.
实际上真正在面试的难度级别上来说, 不会让你想那么复杂, 一般都是你自己脑子里想好什么时候能够取到这个 optimal 的情况,然后写代码实现就行了, 也就是先自己分析转化问题, 比如我这里的这个算法的思路就是转化成了一个bucket sort之后的问题;

不过这个算法有问题, oj 上面一个超大的 case 有index out of bound的 exception, 不知道什么原因;

或许这里题目描述里面的100 000就是为了告诉你不要用bucket sort?
这个也许就是 exception 的原因, 因为 b 的长度太大了.
不对, 这里这个input5也没有报错;
原来就是打错了, line33的i + 100 000打成了i + 10 000;
这个错误的原因是如果有小于-10 000的 i 进来, 那么你找的b 的 index 就是<0了;

最后一行本来是两个 return(if (..) return ...; return ...), 现在改成了一行.
现在这个代码的速度是99%, 很厉害了;

不过这里问题的大概本质已经看出来了, 实际上就是找有多少个distinct values.

Problem Description

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:

The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].
Subscribe to see which companies asked this question.

Hide Tags Hash Table