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

embedded/2024/11/17 20:50:25/

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

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

刷一道题热热身。

题目

在这里插入图片描述

要求

在这里插入图片描述

题目分析

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

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

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

滑动窗口法

使用滑动窗口法来进行解答,因为题目中要求寻找的是数对,也就是两个相同的数字,因此可以设定滑动窗口的大小为2,因为数组本身并不是有序的,所以首先需要对数组进行排序,可以从小到大也可以从大到小,这个对算法没有影响。接着设定两个变量ij,作为滑动窗口,如果窗口中的值是相同的,则向前滑动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;
}

http://www.ppmy.cn/embedded/138339.html

相关文章

IDC机房服务器托管的费用组成

IDC机房服务器托管的费用&#xff0c;并不是只有我们所想的电费而已&#xff0c;还有一些其它费用组成&#xff0c;详细来看&#xff1a; 1. 机位费用&#xff1a;   - 机位费用是根据服务器的尺寸和占用的空间来计算的。服务器通常按照U&#xff08;Unit&#xff09;的高度来…

MFC IDC_STATIC控件嵌入一个DIALOG界面

1.创建一个新的mfc工程 2.在资源视图中新增一个dialog界面 将新增的dialog界面属性中的Border置为None,Style置为Child 右键新增的dialog界面添加类&#xff0c;用于增加类文件 3.在原Dlg文件中增加新dialog文件相关内容 h文件 #include "MyDialog.h" public:…

智能工厂的设计软件 为了监管控一体化的全能Supervisor 的监督学习 之 序5 架构for认知系统 总述 (架构全图)

本文提要 本文讨论的“智能工厂的设计软件” for认知系统的架构全图 &#xff0c;这有别于前面所说的“智能工厂的设计软件”的“全景图”。两者在内容和侧重点上有所不同&#xff0c;但它们共同构成了对智能工厂设计软件的全面描述。 全景图是对智能工厂设计软件的整体概览&…

基于树莓派的边缘端 AI 目标检测、目标跟踪、姿态估计 视频分析推理 加速方案:Hailo with ultralytics YOLOv8 YOLOv11

文件大纲 加速原理硬件安装软件安装基本设置系统升级docker 方案Demo 测试目标检测姿态估计视频分析参考文献前序树莓派文章hailo加速原理 Hailo 发布的 Raspberry Pi AI kit 加速原理,有几篇文章介绍的不错 https://ubuntu.com/blog/hackers-guide-to-the-raspberry-pi-ai-ki…

2024.11.16下午RHCA上课笔记

yum/dnf命令 # 使用yum命令安装软件&#xff0c;首先必须给yum配置软件仓库&#xff0c;安装所有软件都从这个软件仓库中获取。 # 配置目录在 /etc/yum.repos.d/ # 本地仓库配置 # 1.将光盘放入光驱&#xff0c;并且将其挂载到 /mnt/cdrom目录下 # 2.在/etc/yum.repos.d/新…

http自动发送请求工具(自动化测试http请求)

点击下载《http自动发送请求工具(自动化测试http请求)》 前言 在现代软件开发过程中&#xff0c;HTTP 请求的自动化测试是确保应用程序稳定性和可靠性的关键环节。为了满足这一需求&#xff0c;我开发了一款功能强大且易于使用的自动化 HTTP 请求发送工具。该工具基于 C# 开发…

成本400元,DIY一个高刷新率热成像相机

在市面上开源的热成像作品中&#xff0c;有一部分颜值高&#xff0c;但分辨率太低&#xff1b;也有一部分把分辨率提高了&#xff0c;但使用起来却不太流畅。 基于此&#xff0c;作者本人结合二者的优势&#xff0c;设计了一款热成像相机——LiThermal&#xff0c;成本算下来只…

【C语言】前端未来

你对前端未来的技术趋势有何看法&#xff1f;例如WebAssembly、WebXR、PWA等。 对未来前端技术趋势的看法&#xff0c;我认为有几个关键方向正在快速发展&#xff1a; WebAssembly (WASM)&#xff1a;随着性能需求的增长&#xff0c;WebAssembly作为一种低级字节码运行环境&…