【Leetcode】移除后集合的最多元素数

这篇具有很好参考价值的文章主要介绍了【Leetcode】移除后集合的最多元素数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

💡题目描述

💡思路

💡总结



【Leetcode】移除后集合的最多元素数,算法,leetcode,算法



100150. 移除后集合的最多元素数

💡题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,它们的长度都是偶数 n 。

你必须从 nums1 中移除 n / 2 个元素,同时从 nums2 中也移除 n / 2 个元素。移除之后,你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。

返回集合 s可能的 最多 包含多少元素。

【Leetcode】移除后集合的最多元素数,算法,leetcode,算法

💡思路

这道题是求两个数组 nums1 和 nums2 各移除长度的一半元素后,剩余元素组成的集合s可能包含的最大元素数量。

主要思路是:

1.  将nums1和nums2中的元素分别放入两个无序集set1和set2中,统计两个集合的大小n1和       n2,以及公共元素数量common

2.  计算如果不移除任何元素,集合s可能包含的最大元素数量为n1+n2-common

3.  考虑是否需要从set1和set2中各移除长度一半的元素:

  • 如果set1大小大于长度一半,从答案和公共元素中分别减去set1大于长度一半的部分
  • 如果set2大小大于长度一半,也进行同样的减法操作

4.   返回经过以上处理后的最大可能元素数量

主要步骤如下:

  1. 将nums1和nums2中的元素分别放入set1和set2
  2. 统计set1大小n1,set2大小n2,公共元素数量common
  3. 总元素数量为n1+n2-common
  4. 定义长度一半为m
  5. 如果set1大于m,答案和common分别减去set1大于m的部分
  6. 如果set2大于m,也进行同样减法
  7. 返回答案

所以这道题是通过无序集合统计元素情况,并考虑是否需要移除长度一半的元素后,返回集合s可能包含的最大元素数量。

class Solution {
public:
    int maximumSize(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1, set2;
        
        for(int num: nums1) set1.insert(num);
        for(int num: nums2) set2.insert(num);
        
        int n1 = set1.size(), n2 = set2.size();
        int common = 0;
        
        for(int num: set1) {
            if(set2.count(num)) common++; 
        }
        
        int ans = n1 + n2 - common;
        int m = nums1.size()/2; 
        
        if(n1 > m) {
            int mn = min(n1-m, common);
            ans -= n1 - mn - m;
            common -= mn;
        }
        
        if(n2 > m) {
            n2 -= min(n2-m, common); 
            ans -= n2 - m;
        }
        
        return ans;
    }
};

💡总结

主要步骤:

  1. 使用unordered_set存储nums1和nums2元素
  2. 统计set1,set2大小和公共元素数量
  3. 初始答案为set1+set2-公共元素
  4. 定义长度一半为m
  5. 如果set大小大于m,答案和公共元素分别减去大于m部分
  6. 返回最终答案

总的来说就是利用无序集合统计元素情况,并考虑是否需要移除长度一半元素来返回最大可能元素数量。文章来源地址https://www.toymoban.com/news/detail-821901.html

到了这里,关于【Leetcode】移除后集合的最多元素数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode 2114. 句子中的最多单词数

    题目: 一个 句子 由一些 单词 以及它们之间的单个空格组成,句子的开头和结尾不会有多余空格。 给你一个字符串数组 sentences ,其中 sentences[i] 表示单个 句子 。 请你返回单个句子里 单词的最多数目 。 解题方法: 1.遍历列表,获取每个值,将值(字符串)用split转换成列

    2024年02月02日
    浏览(42)
  • leetcode27.移除元素

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【LeetCode】 🍓希望我们一起努力、成长,共同进步。 👉题目链接 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长

    2024年02月05日
    浏览(43)
  • 【LeetCode】27. 移除元素

     题目大概意思是剔除nums数组中出现的所有val值。可以用 快慢双指针法 来做。 快的指针在前面遍历找值不为val的元素的下标,慢的负责接收值不为val的元素,并及时更新数组。  

    2024年02月14日
    浏览(45)
  • LeetCode刷题---移除元素

    2024年02月08日
    浏览(69)
  • LeetCode:移除元素

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明: 为什么返回数

    2024年02月09日
    浏览(35)
  • LeetCode1578. 使绳子变成彩色的最短时间

    拆除成本 = 全部拆除 - 最大的不拆除 在统计成本的同时,维持一个成本的最大值

    2024年02月11日
    浏览(40)
  • LeetCode 203. 移除链表元素

    给你一个链表的头节点  head  和一个整数  val  ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点  。   (1)直接使用原来的链表来进行移除节点操作: (2)设置一个虚拟头结点在进行移除节点操作:

    2024年02月15日
    浏览(36)
  • LeetCode 203.移除链表元素

    力扣题目链接

    2024年01月16日
    浏览(52)
  • 【LeetCode】每日一题:移除元素

    目录  题目: 思想1:暴力解法 思想2:创建一个temp数组  思想3:双指针 👻内容专栏:《LeetCode刷题专栏》 🐨本文概括: 27.移除元素 🐼本文作者:花 碟 🐸发布时间:2023.4.15 https://leetcode.cn/problems/remove-element/   点击跳转到LeetCode平台OJ页面(27.移除元素)  👉 示例1: 解

    2023年04月19日
    浏览(73)
  • Leetcode每日一题——“移除元素”

    各位CSDN的uu们你们好呀,小雅兰又来啦,今天,小雅兰的内容是移除元素,下面,让我们进入Leetcode的世界吧   说明: 为什么返回数值是整数,但输出的答案是数组呢? 请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。 你可以

    2023年04月23日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包