题解 | #手套#

import java.util.*;

public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        int count=0;//定义出现0的情况先.需要先拿几只手套,来简化问题
        int leftSum=0;//左右手手套数量的和
        int rightSum=0;
        int leftMin=Integer.MAX_VALUE;;//左右手手套数量的最小值,一定要定义最大的,这样才能更新得到数组中的最小值,定义为0的话,直接不用比较了,最后的最小值一定是0
        int rightMin=Integer.MAX_VALUE;;
        for(int i=0;i<n;i++){
            if(left[i]*right[i]==0){//出现颜色为0的情况
            count+=left[i]+right[i];//因为不知道是那一只手为0,所以全部加,反正为0,只加另一只手
            }else{//这里处理的是所有的非0的颜色的情况(越过了包含0的下标,不算进去)-->正常情况的,简化了的
            leftSum+=left[i];
            if(leftMin>left[i]){
                leftMin=left[i];//更新最小值
            }
            rightSum+=right[i];
            if(rightMin>right[i]){
                rightMin=right[i];//更新最小值
            }
            }
        }
        //得到了左边的sum,及min及要先拿走的属于0的颜色(右边也一样)
        int minNum=Math.min(leftSum-leftMin+1,rightSum-rightMin+1)+1;//得到简化后的正常所情况需拿的手套数量,拿完,加一
        return count+minNum;//最后的数量是简化后的加上提前拿走的
    }
}

一定能凑出,而且还要最少:所有的最坏的情况发生,然后在最坏情况发生后,只要拿到一次满足条件的手套即可,不再多拿

--->正常情况:没有空白手套的情况:即所有的手套都至少要一只对应(左右手)

--->怎么样才能保证一定能凑出一双手套?

--->发生最坏的情况:左手的拿了4+3+2+1=10只-->所有的颜色(最少的拿种颜色拿一只即可,最坏的情况是把数量多的全部拿了,最后才轮到数量最少的)

--->然后右手随便拿一只即可-->1

--->一共11只必然凑出一双

--->又或者:右手拿了5+3+2+1=11只--->拿到了所有的颜色

--->左手随便拿一只-->1

一共12只必然凑出一双

--->比较左/右手拿完的两种情况最小值,结果取最小即可

---->怎么才能得出某一只手需要几只手套才能一定凑出所有的颜色:所有的手套数量求和,然后减去最小的数量,然后加一(减去最小的,代表现在只剩最小数量的那种颜色没有拿了,+1代表拿了最小数量的那种颜色的手套)

---->2+3+2+4-1+1=10

--->不正常情况:

左右手出现了单独的手套,即某种颜色只有0只的情况

--->我们首先得把0只手套的手对应的另外一只手的颜色全部拿完

--->如:左手0右手1,把1拿了,右手0左手1,把1拿了--->所以先提前拿了2

--->然后就可以简化题目了

--->因为拿了单独手套的颜色的话,它是一定不能凑出一对的,所以这是坏的情况,把它拿了就去掉坏的情况了

--->有0的那只手,即便你拿了所有的颜色,另外一只手只要拿0对应的颜色,就永远凑不出一对,所以必须得先把0对应的颜色拿完,再拿其他颜色才能凑出

---->简化后左右手都只剩两种颜色了,按照正常情况求出要拿多少只即可

--->最后把2加上剩下的正常情况的即可:2+8=10只