
P4305 [JLOI2011]不重复数字
读取输入数据:首先读取输入数据,包括多个测试用例。每个测试用例包含一个整数n和n个数。 初始化数据结构:使用一个哈希表(如unordered_map)来记录已经处理过的数,键是数值,值是一个布尔标记,用于表示该数是否已经被处理过。 遍历并处理数:遍历输入的数,对于每个数,检查它是否已经在哈希表中存在。如果不存在,则将其添加到结果列表中,并记录到哈希表中;如果已经存在,则跳过。 输出结果:将处理后的结果列表按要求格式输出,两个数之间用空格隔开。 读取输入: 写入输出: 主函数:读取测试用例数量,然后处理每个测试用例。使用哈希表记录已处理过的数,遍历输入数组,保留第一次出现的数。 输出结果:将处理后的结果列表转换为字符串并输出。
发布日期:2021-05-07 09:39:59
浏览次数:10
分类:精选文章
本文共 1898 字,大约阅读时间需要 6 分钟。
为了解决这个问题,我们需要去除给定数列中的重复项,只保留第一次出现的数。为了实现这一目标,我们可以使用哈希表来记录已经处理过的数,这样可以快速查找并避免重复记录。
方法思路
这种方法的时间复杂度是O(n),空间复杂度也是O(n),其中n是输入数据的大小。这种方法高效且适用于处理大规模数据。
解决代码
#include#include #include #include using namespace std;void readNumber(long long& x) { x = 0; char ch = ' '; while ((ch = getchar()) != '\0') { if (isdigit(ch)) { x = x * 10 + (ch - '0'); } else if (ch == '-') { x = -x; } else { break; } }}void writeNumber(long long x) { if (x < 0) { putchar('-'); x = -x; } if (x == 0) { putchar('0'); return; } while (x > 0) { putchar(x % 10 + '0'); x /= 10; }}int main() { long long t; readNumber(t); for (long long _ = 0; _ < t; ++_) { long long n; readNumber(n); long long* numbers = new long long[n]; for (long long i = 0; i < n; ++i) { long long num; readNumber(num); numbers[i] = num; } unordered_map seen; vector result; for (long long num : numbers) { if (seen.find(num) == seen.end()) { seen[num] = true; result.push_back(num); } } if (result.empty()) { cout << "" << endl; } else { ostringstream oss; for (size_t i = 0; i < result.size(); ++i) { if (i > 0) { oss << ' '; } writeNumber(result[i]); } cout << oss.str() << endl; } delete[] numbers; } return 0;}
代码解释
readNumber
函数用于读取输入的数值,可以处理负数和多位数。writeNumber
函数用于将数值转换为字符串并输出,处理负数和零的情况。这个方法确保了高效处理和正确输出,适用于处理多个测试用例和大规模数据。
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2025年04月06日 16时44分58秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
数字化助力金融科技,实现产业良性循环
2019-03-04
2020-11-18(失败的一天)
2019-03-04
2020-11-23(彻底理解KMP)
2019-03-04
DMB DSB ISB 简介
2019-03-04
常用的IDC函数
2019-03-04
BUUCTF 新年快乐 内涵的软件 Java逆向解密 刮开有奖
2019-03-04
虎符杯——虚拟机逆向
2019-03-04
angr学习笔记(7)(malloc地址单元符号化)
2019-03-04
angr学习笔记(9)(添加约束)
2019-03-04
angr学习笔记(13)(static_binary)
2019-03-04
windows环境利用start命令实现微信多开
2019-03-04
「CF149D」括号涂色 区间DP好题
2019-03-04
树状数组 模板总结
2019-03-04
「NOI2015」程序自动分析 并查集题解
2019-03-04
[JSOI2008]Blue Mary的战役地图 Hash题解
2019-03-04
Ubuntu修改终端上显示的用户名和主机名(详细步骤)
2019-03-04
教你写一手漂亮的伪代码(详细规则&简单实例)
2019-03-04
MySQL的基本体系和架构介绍
2019-03-04
MySQL数据备份实践和整理
2019-03-04
结构型设计在工作中的一些经验总结
2019-03-04