力扣 —— 2341.数组能形成多少数对
题目链接:数组能形成多少数对
刷一道题热热身。
题目
要求
题目分析
简单的对题目进行分析,可以看出题目的意思是给你一个数组,让你找出这个数组中一共有多少对相同的数字,然后除去这相同的数字数组中又剩下多少数字。并且明确给出1 <= nums.length <= 100
和 0 <= nums[i] <= 100
。
这道题目可以有很多种解法,这里就先使用两种方法来进行解答:
- 使用滑动窗口法来进行解答。
- 使用哈希表法来进行解答。
滑动窗口法
使用滑动窗口法来进行解答,因为题目中要求寻找的是数对,也就是两个相同的数字,因此可以设定滑动窗口的大小为2,因为数组本身并不是有序的,所以首先需要对数组进行排序,可以从小到大也可以从大到小,这个对算法没有影响。接着设定两个变量i
,j
,作为滑动窗口,如果窗口中的值是相同的,则向前滑动2个位置,否则就向前滑动1个位置,因为设定的变量j
始终等于 i + 1
,因此整个窗口的滑动可以只考虑i
,窗口滑动的实现如下:
int ans = 0, remain = nums.size();
int i = 0, j = 0;
while(j < nums.size()) {if(nums[i] == nums[j]) {i += 2;// 此处用于处理数据ans ++;remain -= 2;}else {i ++;}j = i + 1;
}
哈希表法
使用哈希表法进行解答,可以遍历一次数组,得到每个数字出现的次数,然后统计到哈希表中,如果哈希表出现的数字的个数大于2,就说明存在一个数对,然后对每一个数字进行处理即可。
int hash[100 + 10];
// 首先将数组初始化为0,也可以使用vector来进行实现数组。
for(int i = 0;i < 100 + 10; i ++) hash[i] = 0;
// 对每一个数字进行统计
int num = 0;
int ans = 0, remain = nums.size();
for(int i = 0;i < nums.size();i ++) {num = nums[i];hash[num] ++;if(hash[num] == 2){// 如果hash中的数字等于 2 了,就说明存在一个数对ans ++;remain -= 2;hash[num] -= 2;}
}
代码实现
提交代码
滑动数组法
class Solution {
public:vector<int> numberOfPairs(vector<int>& nums) {if (nums.size() == 0) return {0, 0};else if (nums.size() == 1) return {0, 1};int ans = 0, total = nums.size();// 循环输出数对sort(nums.begin(), nums.end());int i = 0, j = 1;while (j < nums.size()) {if (nums[i] == nums[j]){ans ++;total -= 2;i += 2; j = i + 1;// cout<<nums[i]<<" "<<nums[j]<<endl;}else {i++; j = i + 1;}}return {ans, total};}
};
结果:
哈希表法
class Solution {
public:vector<int> numberOfPairs(vector<int>& nums) {if(nums.size() == 0) return {0, 0};if(nums.size() == 1) return {0, 1};// 方法二:哈希表法const int int_max = 100 + 10;int hash [int_max];int ans = 0, total = nums.size();// 赋初值为 0for(int i = 0;i < int_max; i++) hash[i] = 0;for(int i = 0;i < nums.size(); i ++) {hash[nums[i]] ++;if(hash[nums[i]] == 2) {ans ++;total -= 2;hash[nums[i]] -= 2;}}return {ans, total};}
};
结果:
调试代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);void Print(vector<int> nums){for(auto v : nums) {cout<<v<<" ";}cout<<endl;}vector<int> solve_2(vector<int> nums) {if(nums.size() == 0) return {0, 0};if(nums.size() == 1) return {0, 1};// 方法二:哈希寻找法const int int_max = 100 + 10;int hash [int_max];int ans = 0, total = nums.size();// 赋初值为 0for(int i = 0;i < int_max; i++) hash[i] = 0;for(int i = 0;i < nums.size(); i ++) {hash[nums[i]] ++;if(hash[nums[i]] == 2) {ans ++;total -= 2;hash[nums[i]] -= 2;}}return {ans, total};
}vector<int> solve_1(vector<int> nums) {// 方法一:滑动窗口法if (nums.size() == 0) return {0, 0};else if (nums.size() == 1) return {0, 1};int ans = 0, total = nums.size();// 循环输出数对sort(nums.begin(), nums.end());int i = 0, j = 1;while (j < nums.size()) {if (nums[i] == nums[j]){ans ++;total -= 2;i += 2; j = i + 1;// cout<<nums[i]<<" "<<nums[j]<<endl;}else {i++; j = i + 1;}}return {ans, total};
}int main(){IOS int t = 1;vector<int> nums = {1,3,2,1,3,2,2};// vector<int> nums = {1, 1};while(t --) {vector<int> ans = solve_2(nums);cout<<ans[0]<<' '<<ans[1]<<endl;}return 0;
}