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; } else cnt1++; 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. 数组能形成多少数对】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
