排序 - 强迫症买香蕉

纷纷扰扰的世界有很多强迫症，我就是一个爱吃香蕉的强迫症，我去水果店买香蕉，按筐买，我的要求是买回来的每一筐必须有相同数量的香蕉，我通常的做法是：
<1>取出筐里的一部分香蕉不要
<2>整筐香蕉都不要
那你知道我最多能买到多少香蕉呢？

举列：
水果店每个筐里的香蕉：【1】【2】【3】，则最多买到香蕉：4个
水果店每个筐里的香蕉：【5】【0】【29】【14】，则最多买到香蕉数：29个

问题解析：

1. 按筐里的香蕉个数进行排序。

例如：水果店每个筐里的香蕉：【5】【0】【29】【14】，排序后为：【0】【5】【14】【29】

2. 根据排序结果，从小到大选择筐中香蕉个数，来计算每次选择能买到的最多香蕉数。

选择方案如下：
<1>选择在筐里装【0】个香蕉，则最多能买到0个香蕉

<2>选择在筐里装【5】个香蕉，则舍弃第一筐，买走第二筐【5】，第三筐买走5根，其余舍弃，第四筐买走5根，其余舍弃，则最多能买到的香蕉数为：5 + 5 + 5 = 15

<3>选择在筐里装【14】根香蕉，则舍弃第一框，第二筐，买走第三筐【14】，第四筐买走14根，其余舍弃，则最多能买到的香蕉数为：14 + 14 = 28

<4>选择在筐里装【29】根香蕉，则舍弃第一筐，第二筐，第三筐，买走第四框【29】，则最多能买到的香蕉数为：29

所有选择方案中，能买到的最多香蕉数为29

3. 数据模型

假设水果店有10筐香蕉，我们将每筐的香蕉数对应放到一个数组a中，即：a = [0, 5, 14, 28, 6, 9, 9, 29, 11, 17]，a.length = 10

对数组a进行排序：[0, 5, 6, 9, 9, 11, 14, 17, 28, 29]

依次选择a数组中的每个元素，作为选择买走的每筐香蕉数：(max表示能买到的最大香蕉数)

选择筐里装a[0]根香蕉，则max₀ = a[0] * (a.length - 0)
选择筐里装a[1]根香蕉，则max₁ = a[1] * (a.length - 1)
选择筐里装a[2]根香蕉，则max₂ = a[2] * (a.length - 2)
...
选择筐里装a[i]根香蕉，则maxᵢ = a[i] * (a.length - i)

注意：
这里有个问题：a数组中含有重复的元素9，9，如果按上面的规则：
第一个9，对应a[3]，则max₃ = a[3] * (a.length - 3) = 63
第二个9，对应a[4]，则max₄ = a[4] * (a.length - 4) = 54
而实际的情况是选择筐里装9根香蕉时，能买走的最大香蕉数是相等的，都为63，
但此问题不影响最终计算买到最大香蕉数的这个结果。

解决：
针对于第二个重复元素问题，我们可以借助map结构进行处理：
key = a[i]，value = maxᵢ
对于选择数组a中的元素a[i]，先判断是否在map中，若存在，则从map中获取值并赋值给maxᵢ，否则将计算得到的maxᵢ放到map中。

代码实现

对数组a使用快速排序，然后遍历数组a，依次计算并比较，最终得出能买到最多的香蕉数。
（数组a中的重复元素，不影响最终结果，因此忽略对其特殊处理）

    public static int getMaxBananaNumber(int[] a) {
        if (a == null) {
            return 0;
        }
        if (a.length == 1) {
            return a[0];
        }
        quickSort(a, 0, a.length - 1);

        int max = 0;
        for (int i = 0,len = a.length; i < len; i++) {
            max = Math.max(a[i] * (len - i), max);
        }
        return max;
    }

    public static void quickSort(int[] a, int start, int end) {
        if (start < end) {
            int mid = partition(a, start, end);
            quickSort(a, start, mid-1);
            quickSort(a, mid+1, end);
        }
    }

    private static int partition(int[] a, int start, int end) {
        int i = start - 1;
        int p = a[end];
        for (int j = start; j <= end-1; j++) {
            if (a[j] <= p) {
                i++;
                exchange(a, i, j);
            }
        }
        exchange(a, i+1, end);
        return i+1;
    }

    private static void exchange(int[] a, int frontIndex, int laterIndex) {
        int temp = a[frontIndex];
        a[frontIndex] = a[laterIndex];
        a[laterIndex] = temp;
    }