1. 项目概述一道经典的“去重排序”入门题如果你刚开始接触信息学竞赛或者正在学习C、Java等编程语言的数据结构基础那么“明明的随机数”这道题几乎是一个绕不开的里程碑。它频繁出现在《信息学奥赛一本通》、OpenJudge、洛谷等各大OJ平台题号可能不同但核心完全一致。我第一次接触这道题时觉得它简直是为初学者量身定做的“完美练习题”——它不涉及复杂的算法思想却巧妙地串联起了数组操作、排序和去重这几个最基础、最核心的编程概念。这道题描述了一个非常生活化的场景明明生成了N个1到1000之间的随机整数现在需要你帮忙完成“去重”与“排序”两项工作。最终输出两个结果第一行是去重后剩余不同数字的个数第二行是这些数字按从小到大排序后的序列。题目本身简单直接但正是这种简单让它成为了检验你是否真正掌握基础数据处理能力的试金石。很多同学在学习了sort函数和set集合后会觉得这道题索然无味但你是否想过如果不允许使用STL库你能否仅用数组和基本循环就优雅地解决它这道题的价值恰恰在于它逼迫你去思考数据处理的本质。2. 核心需求与解题思路拆解2.1 问题本质数据清洗与整理我们抛开“明明”这个背景将问题抽象一下你手头有一批可能存在重复的数据整数你的任务是对这批数据进行清洗剔除重复项然后按照一定的规则这里是升序进行整理输出。这在实际编程中太常见了比如统计用户ID、处理日志中的IP地址、分析商品编号等。题目将数据范围限定在1-1000且N≤100这个设定非常友好意味着我们可以使用一些“朴素”但高效的方法。2.2 核心步骤分解无论采用哪种方法解决这个问题的逻辑流程都可以分解为以下三步输入与存储读取整数N然后循环N次读取随机数将它们存入一个容器如数组、向量或集合。去重与排序这是算法的核心。需要消除容器中的重复元素并将剩余元素按升序排列。注意去重和排序的顺序可以互换不同的顺序会衍生出不同的解题策略。输出结果第一行输出去重后的元素个数M第二行输出这M个已排序的元素用空格隔开。2.3 方法选型背后的考量为什么这道题会有多种解法因为它处于一个复杂度与代码量的“甜蜜点”。数据量小N≤100数值范围1-1000使得从O(N²)到O(N log N)甚至O(N)的算法都在可接受范围内。这就允许我们根据不同的学习阶段和编程语言特性选择最合适的工具初学者/巩固基础应优先使用数组和基本循环手动实现去重和排序如冒泡排序遍历去重这能深刻理解过程。掌握STL的C选手使用sort和unique函数组合是比赛中最快捷、不易出错的“标准答案”。利用数据结构特性直接使用set或unordered_set后去重其自动排序和去重的特性让代码极其简洁。利用数值范围使用“桶”的思想标记数组可以达到理论上的O(N)时间复杂度这是一种空间换时间的典型思路。选择哪种方法取决于你的目的。如果是练习我强烈推荐从数组手动实现开始如果是竞赛中快速解题那么sortunique或set是不二之选。3. 四种经典实现方案详解下面我将分别用四种典型的C实现方案来解析这道题并附上详细的注释和对比。你可以清晰地看到从“底层实现”到“高级抽象”的演进过程。3.1 方案一纯数组 手动冒泡排序与去重这是最“原始”的方法不依赖任何现成的库函数适合初学者理解每一个步骤。#include iostream using namespace std; int main() { int n; int nums[101]; // 根据题意N最大为100多开一个位置防止越界 cin n; // 1. 输入数据 for (int i 0; i n; i) { cin nums[i]; } // 2. 排序这里使用冒泡排序易于理解 for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (nums[j] nums[j 1]) { // 交换 int temp nums[j]; nums[j] nums[j 1]; nums[j 1] temp; } } } // 3. 去重并统计个数 int m 0; // m用于记录去重后数组的有效长度也作为新数组的下标 for (int i 0; i n; i) { // 如果是第一个元素或者当前元素不等于上一个有效元素则保留 if (i 0 || nums[i] ! nums[m - 1]) { nums[m] nums[i]; // 将不重复的元素移到数组前部 m; } // 如果nums[i] nums[m-1]说明是重复元素直接跳过i继续循环 } // 4. 输出结果 cout m endl; for (int i 0; i m; i) { cout nums[i] ; } cout endl; // 输出换行符合格式要求 return 0; }核心要点与避坑指南数组大小题目说N≤100但数组最好声明为[101]或更大这是一个良好的防越界习惯。去重逻辑这段去重代码非常经典。它利用了数组已排序的特性。m指针始终指向“去重后数组”的末尾下一个位置。当遍历原数组nums[i]时只将与nums[m-1]即当前去重数组最后一个元素不同的元素追加到去重数组末尾。这个操作直接在原数组上进行节省了空间。为什么先排序再去重对于无序数组去重需要将每个元素与之前所有元素比较复杂度为O(N²)。排序后重复元素必然相邻只需一次遍历O(N)即可完成去重总复杂度取决于排序算法冒泡为O(N²)。先排序再去重是更优的策略。3.2 方案二C STLvectorsortunique这是竞赛中最常用、最规范的写法兼具效率与简洁。#include iostream #include vector #include algorithm // 包含sort和unique using namespace std; int main() { int n; cin n; vectorint nums(n); // 直接初始化大小为n的vector for (int i 0; i n; i) { cin nums[i]; } // 1. 排序 sort(nums.begin(), nums.end()); // 2. 去重。unique函数将不重复的元素移到前面并返回去重后新序列的尾后迭代器 auto new_end unique(nums.begin(), nums.end()); // 3. 计算去重后大小并输出 int m new_end - nums.begin(); // 迭代器相减得到元素个数 cout m endl; // 4. 输出去重后的元素 for (auto it nums.begin(); it ! new_end; it) { cout *it ; } cout endl; return 0; }核心要点与避坑指南unique函数的行为这是关键std::unique并不会删除容器中的元素也不会改变容器的size()。它只是将相邻的重复元素“移动”到容器末尾并返回一个指向第一个被移动的重复元素即新逻辑序列末尾的迭代器。容器nums在unique之后[begin(), new_end)区间是不重复的有序序列而[new_end, end())区间是重复元素的“残留”其值是不确定的。如何真正删除元素如果后续操作需要干净的容器可以调用nums.erase(new_end, nums.end())。但本题只需输出所以不需要erase。迭代器计算个数new_end - nums.begin()是得到去重后个数的标准写法因为随机访问迭代器支持相减操作。3.3 方案三利用set自动去重排序这是代码最简洁的方案充分利用了STL容器的特性。#include iostream #include set using namespace std; int main() { int n, temp; cin n; setint s; // set会自动排序默认升序且去重 for (int i 0; i n; i) { cin temp; s.insert(temp); // 插入操作重复元素不会被插入 } // 输出 cout s.size() endl; // 大小即为去重后个数 for (auto it s.begin(); it ! s.end(); it) { cout *it ; } cout endl; return 0; }核心要点与避坑指南set的底层与复杂度set通常基于红黑树实现每次insert操作的复杂度是O(log N)总复杂度为O(N log N)。虽然和sort一样但常数可能略大。对于本题数据量完全无感。unordered_set不行如果你想用unordered_set哈希集合来只去重会发现它不保证元素顺序输出时还需要额外排序反而不如set方便。简洁性的代价此方法代码量最小逻辑最清晰。但在一些对性能极其苛刻或禁止使用STL的场景下需要回到方案一或方案四。3.4 方案四“桶排序/标记法”思路这是一种非常巧妙的O(N)方法利用了题目中“随机数是1到1000之间的整数”这个限定条件。#include iostream using namespace std; int main() { int n, temp; cin n; bool bucket[1001] {false}; // 下标1-1000初始化为false表示该数字未出现 int count 0; // 1. 读入并标记 for (int i 0; i n; i) { cin temp; if (!bucket[temp]) { // 如果这个数第一次出现 bucket[temp] true; // 标记为已出现 count; // 统计不同数字的个数 } // 如果已经为true说明重复忽略 } // 2. 输出个数 cout count endl; // 3. 输出数字天然有序因为我们是按下标1-1000遍历的 bool first true; // 用于控制空格输出第一个数前不输出空格 for (int i 1; i 1000; i) { if (bucket[i]) { if (!first) { cout ; } cout i; first false; } } cout endl; return 0; }核心要点与避坑指南空间换时间的典范我们创建了一个大小为1001的布尔数组“桶”下标对应数字本身。读入数字temp时直接将bucket[temp]标记为true。这个过程同时完成了去重重复标记无效和排序输出时只需从1到1000遍历值为true的就输出顺序自然是升序。时间复杂度读入和标记O(N)输出遍历O(1000)总复杂度O(N1000)对于本题范围几乎是线性时间。局限性此方法严重依赖数据范围小且已知的前提。如果数字范围是-10^9到10^9这种方法将因需要巨大空间而不可行。但它完美契合了本题条件展示了根据数据特征选择算法的智慧。输出格式技巧使用first标志位来控制空格的输出避免了末尾多空格的常见格式错误比在循环内判断i是否最后一个有效数字更简洁。4. 方案对比与场景选择为了更直观地理解四种方案的差异我整理了下面的对比表格特性方案一纯数组手动方案二vectorsortunique方案三set方案四桶标记法核心思想手动实现排序和去重利用STL算法组合利用容器的自动排序去重特性利用数值范围用下标直接标记时间复杂度O(N²) (冒泡排序)O(N log N) (快速排序)O(N log N) (红黑树插入)O(N K), K为数值范围(1000)空间复杂度O(N)O(N)O(N)O(K), K为数值范围(1000)代码复杂度较高需自己控制细节中等理解unique行为是关键极低几乎无需处理细节低逻辑简单直接优点锻炼基本功不依赖库效率高STL标准写法代码极其简洁明了理论速度最快思路巧妙缺点/局限效率低代码长需理解迭代器和unique的副作用常数时间可能略大依赖STL严重依赖数据范围空间可能浪费推荐使用场景初学阶段巩固基础竞赛通用解法快速可靠追求代码简洁数据量不大时题目明确限定小范围正整数时个人经验与选择建议在我的刷题和教学经验中对于这道题如果你是初学者请务必亲手实现一遍方案一。这个过程能让你透彻理解“排序”和“去重”这两个基本操作是如何在内存中一步步完成的。这是内功绕不开。当你准备参加考试或竞赛方案二是你的首选。它平衡了效率、代码量和可读性是专业选手的标配。务必熟练掌握sort和unique的配合。当你在开发中快速实现一个小功能或者在做题追求最短代码时方案三用set是最舒服的。当你看到题目数据范围很小比如本题1-1000一定要想到方案四。这是一种典型的“桶”或“哈希”思想在特定条件下威力巨大能帮你写出时间复杂度最优的代码。5. 常见错误与调试技巧实录即便是一道简单题新手也容易踩坑。下面是我从大量学生提交的代码中总结出的高频错误点。5.1 格式错误多余的空格或换行这是OJ判题最常见的错误之一。题目要求第二行数字间用空格隔开但行末不能有多余空格。错误示例for (int i 0; i m; i) { cout nums[i] ; // 这样会在最后一个数字后面也输出一个空格 }正确写法多种方法A第一个元素特殊处理cout nums[0]; for (int i 1; i m; i) { cout nums[i]; }方法B使用标志位如前文方案四所示方法C使用条件判断适用于知道最后一个元素下标的情况for (int i 0; i m; i) { if (i 0) cout ; // 不是第一个就先输出空格 cout nums[i]; }5.2 去重逻辑错误在手动实现时去重逻辑写错导致漏掉某些情况或数组越界。错误示例1未排序就去重或去重逻辑只比较相邻元素但数组未排序。错误示例2使用双重循环去重时在删除元素或覆盖元素后循环变量处理不当导致跳过元素或访问越界。建议对于初学者最稳妥的方法是先排序再用一个循环和单个指针进行去重如方案一所示这个逻辑最清晰不易出错。5.3 对unique函数的误解以为unique之后容器的size()就变了直接遍历整个容器输出。错误示例unique(nums.begin(), nums.end()); cout nums.size() endl; // 错误size()没有变 for (int num : nums) { // 错误会输出残留的重复元素 cout num ; }牢记unique返回的是新的逻辑结尾迭代器物理容器大小不变。必须用返回的迭代器来计算个数和界定输出范围。5.4 数组越界声明数组int a[100]但循环时for (int i0; in; i)或者cin a[i]时i可能等于n。养成习惯数组大小声明为N10是一个有效的防御策略。5.5 调试技巧小数据测试自己构造包含重复、无序、边界值如N1所有数相同所有数都不同的测试数据。输入5 [1, 2, 2, 3, 1]预期输出3\n1 2 3输出中间变量在排序后、去重后分别打印整个数组观察数据变化是否符合预期。使用在线调试器像洛谷、Codeforces等平台都提供简单的在线调试功能可以单步执行查看变量值。对比输出将你的程序输出与已知正确的程序输出或手算结果进行逐行对比能快速定位问题出在个数统计还是序列输出上。6. 从本题延伸的编程思维训练“明明的随机数”的价值远不止于AC一道题。它像一颗种子能延伸出许多重要的编程思维和技能点。6.1 理解“空间换时间”与“时间换空间”方案四桶标记法是典型的“空间换时间”。我们用了1001个布尔变量的空间换来了接近O(N)的线性时间。反之如果内存极其紧张我们可能需要在时间上进行妥协。这种权衡在算法设计中无处不在比如哈希表空间换时间和链表节省空间但访问慢。6.2 掌握数据处理的“管道”思想这道题的解决过程像一个数据处理管道原始数据 - 排序 - 去重 - 输出。在现代数据处理框架如Python的pandas数据库的SQL中这种“声明式”的链式操作非常普遍。sort和unique的组合就是这种思想的体现。你可以思考如果需求变成“去重 - 排序”或者“只去重不排序”管道应该如何调整6.3 举一反三变种题目当你熟练掌握本题后可以尝试解决它的变种巩固知识去重但不排序输出去重后的元素但保持它们在原序列中的第一次出现顺序。这需要你用unordered_set记录出现过的元素并用另一个vector保存顺序。统计每个数的出现次数这就不再是简单的去重而是“计数”。桶标记法可以轻松升级为int bucket[1001]来计数。大数据范围去重排序如果数字范围是-10^9到10^9但N只有10^5你还能用桶吗这时set或sortunique依然是可靠选择你需要理解算法适用范围的变化。6.4 编码习惯与鲁棒性即使题目简单也要写出健壮的代码。比如数组开大一点int nums[110]比int nums[100]更安全。变量命名清晰用unique_end而不是it用count而不是c。处理输入边界虽然本题保证N0但养成习惯考虑如果N0程序是否会崩溃。这道“明明的随机数”就像编程世界里的“Hello World”之后的第一道关卡它平静地站在那里检验着你是否真的准备好了处理数据的基本功。我见过很多同学为了追求刷题量直接用set一行代码AC后就匆匆离开这非常可惜。停下来用几种方法都实现一遍思考其中的差异你会收获的远不止一个绿色的“Accepted”标志而是对程序如何操作数据的一种扎实的、直觉性的理解。这种理解会在你未来面对更复杂的字符串处理、图论建模、动态规划状态设计时悄然发挥巨大的作用。
