当前位置: 首页 > news >正文

Leetcode 每日一题 2341. 数组能形成多少数对

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     我会一直往里填充内容哒!

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

 

这道题十分的简单 给出了两种做法,一种自己写的 一种官解,都有可取之处

目录

题目:

白话讲解:

题例:

题解:

排序消除法:

代码实现:

官解:哈希表:

代码实现:

完结撒花:


题目:

给你一个下标从 0 开始的整数数组 nums 。在一步操作中,你可以执行以下步骤:

  • 从 nums 选出 两个 相等的 整数
  • 从 nums 中移除这两个整数,形成一个 数对

请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案,其中 answer[0] 是形成的数对数目,answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

白话讲解:

返回数组中相同数字的对数,以及不成对数字的个数

题例:

输入:nums = [1,3,2,1,3,2,2]
输出:[3,1]
解释:
nums[0] 和 nums[3] 形成一个数对,并从 nums 中移除,nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对,并从 nums 中移除,nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对,并从 nums 中移除,nums = [2] 。
无法形成更多数对。总共形成 3 个数对,nums 中剩下 1 个数字。

输入:nums = [1,1]
输出:[1,0]
解释:nums[0] 和 nums[1] 形成一个数对,并从 nums 中移除,nums = [] 。
无法形成更多数对。总共形成 1 个数对,nums 中剩下 0 个数字。

题解:

排序消除法:

将数组进行排序,此时若有成对出现的数字必然是相邻的,所以创建两个指针,对相邻的数进行判断.

若这两个数字相同,则计数,i指针跳到下一对数字,

若这两个数字不同,则计数,i往下移一位

最后就是当i==n-2的时候为什么直接让不同数字的计数器直接加1呢?

我们来分析以下上面情况会使i==n-2 

1:当出现 最后两个数字不同的时候,此时只会将计数器+1,但因为最后两位了 也就是n-2的情况,所以直接再+1就行了

 2:当出现倒数第三个与倒数第二个数字相同的时候,此时i变位到j的地方,因为最后也只剩下一位数字了,也已经不可能相同了,所以直接+1就可以

也就是说,当i经历完之前的判断时,他指向的数字位数是倒数第二位的时候,无论如何最后一位都不可能与其相同(若相同 则在if中就前进了一步)

代码实现:

class Solution {
public:vector<int> numberOfPairs(vector<int>& nums) {int n=nums.size(),cnt=0,cnt1=0;if(n==1)return{0,1};sort(nums.begin(),nums.end());for(int i=0,j=1;i<n-1;){   j=i+1;if(nums[i]==nums[j]){cnt++;i=j;}elsecnt1++;if(i==n-2)cnt1++;i++;}return {cnt,cnt1};}
};

官解:哈希表:

创建一个以数字为key,bool值为value的哈希表,初始值均为false,

之后遍历读入每一个数字,若这个数字对应的value为false 则置为true,反之 

若被置为false 则计数器++,未成对出现的数字个数就为总长度减去成对出现的个数*2

代码实现:

class Solution {
public:vector<int> numberOfPairs(vector<int>& nums) {unordered_map<int, bool> cnt;int res = 0;for (int num : nums) {if (cnt.count(num)) {cnt[num] = !cnt[num];} else {cnt[num] = true;}if (!cnt[num]) {res++;}}return {res, (int)nums.size() - 2 * res};}
};

完结撒花:

🌈本篇博客的内容【Leetcode 每日一题 2341. 数组能形成多少数对】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!

http://www.lryc.cn/news/8470.html

相关文章:

  • 前后端分离-小项目-3前后端交互
  • Spring如何整合MyBatis框架?使用XML及java类的配置方式
  • 第七届蓝桥杯省赛——8冰雹数(递归)
  • Android 10.0 设置静态ip重启后获取不到ip的修复
  • mysql笔记
  • 华为OD机试 - 最多等和不相交连续子序列(Python)| 真题+思路+考点+代码+岗位
  • 第四届宁波网安市赛训练题
  • Windows中MySQL 8.x版本忘记密码如何重设
  • 【信管12.1】信息文档管理与配置管理
  • 一文搞懂Linux的标准输出/错误重定向
  • 【OJ】计数的梦
  • 【项目实战】MySQL使用CONCAT字符串拼接函数实现与特殊字符的拼接
  • OpenCV实战(11)——形态学变换详解
  • SPI协议详解(Standard SPI、Dual SPI和Queued SPI)
  • 【代码随想录二刷】Day15-二叉树-C++
  • C++为什么能重夺年度语言?
  • 视频监控实时接入——以海康威视为例(2023.2.16)
  • 推荐系统[一]:超详细知识介绍,一份完整的入门指南,解答推荐系统是什么。
  • 新手小白入门必看!如何批量注册Twitter账号?
  • 虚拟环境的创建以及labelme的使用教程
  • CSS中的BFC详细讲解(易懂)
  • 华为3面,官网显示面试通过了...开始泡池子,进入漫长等待期
  • 【新2023】华为OD机试 - 构成的正方形数量(Python)
  • ElasticSearch之RestClient操作索引库和文档
  • Lp正则化
  • 云原生 -- Docker进阶(Docker-compose,Docker网络简单介绍)
  • taskset命令:让进程运行在指定CPU上
  • Pod基本概念与Pod应用生命周期
  • DDL 数据定义语言
  • 设计模式概述