题解 | #手套#

思路：贪心算法。本题两个数组有两个特点：

1.left 和 right 里都有可能有为零元素。这意味着总数count必须加上对应为0的元素的值，比如left[0]=0,right[0]=8，count就要加8，因为最坏情况从right里取8个可能都取到right[0]了，也就相当于无效组不成一对。所以双方先把这些无效的排了。

贪心算法就是算上最坏情况求最优解，第二步算最优解，由第一个特点知有0的元素对应另一边的元素相当于无效，已经计入count所以我们不再考虑，我们将其设为0。得到新的left和right数组。

2.最优解：从两边总数小的一方入手。这时数组元素都有效（所谓有效就是两边都可能抽中成对），我们只需要考虑到总值小的一方的所有情况。这里又是数学问题，比如从 [2,3,5,8] 最少取多少个能确保4种都取到？思路是涵盖除了最小的三种后再取一个必定能取到第四种，为什么是涵盖除了最小的三种不是留下最大的？比如 [2,3,5,8]这里面我们留下最大的8，取2+3+5+1=11个，可是如果取到的11按最坏情况其他三种不能都取到，我们需要确保4种一定能取到，要取最坏情况，因此应该取8+5+3+1=17个。

考虑了总值小的最坏情况，最后结果+1也就是任意从总值大的一方取一个手套必定能成对。

比如输入 4, [0,7,1,6],[1,5,0,6]。

第一步按最坏情况考虑无效的“0”,count+=1+1. 经过第一步让left变成[0,7,0,6], right变成 [0,5,0,6]。由于7+6>5+6，我们考虑右边即right一方的最坏情况，我们需要排序从大到小取，[0,0,5,6]，由于前两个无效所以不用取，结果就是从right里再取 6+1个，

最后再从left里任意取一个必定能成一对。

import java.util.*;

public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        // write code here
        int count = 0;//总数
	  //count计入无效元素，考虑最坏情况，将为0的对称元素也设为0.
        for (int i = 0; i < n; i++) {
            if(left[i]==0){
                count+=right[i];
                right[i]=0;
            }
            if(right[i]==0){
                count+=left[i];
                left[i]=0;
            }
        }
	    int a = 0;
        int b = 0;
        for (int i = 0; i < n; i++) {
            a+=left[i];
            b+=right[i];
        }
	  //这里为了方便后面做个判断，默认设为 left>right 统一对right做处理。
        if(a<b){
            int[] x = left;
            left = right;
            right = x;
        }
        Arrays.sort(right);//对right排序
	  //对 right 数组取值确保有效值都能涵盖，最坏情况right无0取到right[1]。
        for (int i = n-1; i > 0; i--) {
            if(right[i-1]!=0) count+=right[i];
            else break;
        }
        count++;//从 right 的最后一种任意取一个，确保right每种手套都涵盖
        count++;//从 left 里任意取一个
        return count;
    }
}

总结：

其实就两步：1.排除干扰最优选择的无效元素。2.进行贪心取最优。