力扣 —— 2341.数组能形成多少数对

力扣 —— 2341.数组能形成多少数对

题目链接：数组能形成多少数对

刷一道题热热身。

题目

要求

题目分析

简单的对题目进行分析，可以看出题目的意思是给你一个数组，让你找出这个数组中一共有多少对相同的数字，然后除去这相同的数字数组中又剩下多少数字。并且明确给出1 <= nums.length <= 100 和 0 <= nums[i] <= 100。

这道题目可以有很多种解法，这里就先使用两种方法来进行解答：

1. 使用滑动窗口法来进行解答。
2. 使用哈希表法来进行解答。

滑动窗口法

使用滑动窗口法来进行解答，因为题目中要求寻找的是数对，也就是两个相同的数字，因此可以设定滑动窗口的大小为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();
        // 赋初值为 0
        for(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();
    // 赋初值为 0
    for(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;
}