logo标志,整站建设和网站优化,企业网站不备案可以吗,广告sdk接入题目链接 Leetcode.2341 数组能形成多少数对 Rating : 1185 题目描述
给你一个下标从 0 开始的整数数组 nums。在一步操作中#xff0c;你可以执行以下步骤#xff1a;
从 nums选出 两个 相等的 整数从 nums中移除这两个整数#xff0c;形成一个 数对
请你在 nums上多次执…题目链接 Leetcode.2341 数组能形成多少数对 Rating : 1185 题目描述
给你一个下标从 0 开始的整数数组 nums。在一步操作中你可以执行以下步骤
从 nums选出 两个 相等的 整数从 nums中移除这两个整数形成一个 数对
请你在 nums上多次执行此操作直到无法继续执行。
返回一个下标从 0 开始、长度为 2 的整数数组 answer作为答案其中answer[0]是形成的数对数目answer[1]是对 nums尽可能执行上述操作后剩下的整数数目。
示例 1 输入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 个数字。 示例 2 输入nums [1,1] 输出[1,0] 解释nums[0] 和 nums[1] 形成一个数对并从 nums 中移除nums [] 。 无法形成更多数对。总共形成 1 个数对nums 中剩下 0 个数字。 示例 3 输入nums [0] 输出[0,1] 解释无法形成数对nums 中剩下 1 个数字。 提示
1nums.length1001 nums.length 1001nums.length1000nums[i]1000 nums[i] 1000nums[i]100
分析
直接用 哈希表 记录遍历过的数字模拟这个过程。
时间复杂度O(n)O(n)O(n)
C代码
class Solution {
public:vectorint numberOfPairs(vectorint nums) {int n nums.size();unordered_setint uset;//能匹配的对数int cnt 0;for(auto x:nums){if(!uset.count(x)){uset.insert(x);}else{cnt;uset.erase(x);}}return {cnt,n - 2*cnt};}
};Java代码
class Solution {public int[] numberOfPairs(int[] nums) {SetInteger set new HashSet();int n nums.length;int cnt 0;for(int x:nums){if(!set.contains(x)) set.add(x);else{cnt;set.remove(x);}}return new int[]{cnt,n-2*cnt};}
}
