题解 | 【C++】手套

手套

http://www.nowcoder.com/questionTerminal/365d5722fff640a0b6684391153e58d8

解题思路

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

  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)。
全部评论

相关推荐

吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务