解题思路

我们的目的是要求出最少一共拿多少只手套，才可以保证至少有一对配对的手套。我们可以考虑左右手套分开拿。

  1. 如果某种颜色的手套没有对应配对的另外一只手套的话，为了防止最差情况即：最终全拿到的是这样颜色手套。那就保证至少要把这些数量的手套拿走，其效果相当于以选代ban。

代码：if( left[i] * right[i] == 0) sumBare++;

  1. 接下来我们可以假设剩下这样的场景：剩下颜色的手套，左右手至少都有一只可以配对。我们分别记录剩下的左、右手的手套数量的总和，及其每只手中最少数量的大小。首先保证其中一只手的所有颜色都能拿到，且数量最少的颜色只拿一只，这样就做到了以最少的数量，拿到其中一只手的所有颜色的手套，接下来只需在另外一只手的手套里随便拿一只即可。

代码：min( sumLeft - minleft + 1, sumRight -minRight + 1) + 1;

  1. 最后加上第一步中没有配对的，仅有一只手的手套数量的总和，就是最终返回的结果。

return sumBare + min( sumLeft - minleft + 1, sumRight -minRight + 1) + 1;

代码实现

public:
    int findMinimum(int n, vector<int> left, vector<int> right)
    {
      // 分别记录左右手中数量最少的手套的数量
      int minLeft = INT_MAX;
      int minRight = INT_MAX;
      // 分别记录左右手都有的某种颜色的手套数量的总和
      int sumLeft = 0;
      int sumRight = 0;
      // 合并记录左右手中没有配对颜色的手套的数量
      int sumBare = 0;
      // 根据下标对应的颜色同时遍历上面两个数组，完成上面定义变量的统计
      for(int i = 0; i < n; ++i)
      {
        if(left[i]*right[i] == 0)
        {
          sumBare += left[i]+right[i];
        }
        else 
        {
          sumLeft += left[i];
          sumRight += right[i];
          minLeft = min(minLeft, left[i]);
          minRight = min(minRight, right[i]);
        }
      }
      // 最终结果返回
      return sumBare + min(sumLeft - minLeft + 1, sumRight - minRight + 1) +1;
    }
};

性能分析

  • 时间复杂度：O(n)。两个长度相同的数组同时遍历一遍。
  • 空间复杂度：O(1)。