【GESP】C++三级练习 luogu-B2098 整数去重

GESP C++三级练习，一维数组练习，难度★★☆☆☆。

luogu-B2098 整数去重

题目要求

题目描述

给定含有 $n$ 个整数的序列，要求对这个序列进行去重操作。所谓去重，是指对这个序列中每个重复出现的数，只保留该数第一次出现的位置，删除其余位置。

输入格式

输入包含两行：

第一行包含一个正整数 $n$（$1 \le n \le 20000$），表示第二行序列中数字的个数；

第二行包含 $n$ 个整数，整数之间以一个空格分开。每个整数大于等于 $10$ 、小于等于 $100$。

输出格式

输出只有一行，按照输入的顺序输出其中不重复的数字，整数之间用一个空格分开。

输入输出样例 #1

输入 #1

5
10 12 93 12 75

输出 #1

10 12 93 75

---

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：
   • 对输入的数字序列进行去重
   • 保留每个数字第一次出现的位置
2. 解题关键：
   • 遍历输入序列中的每个数字
   • 检查当前数字是否已经出现过
   • 只保留第一次出现的数字
3. 实现思路：
   • 使用一个数组存储输入的序列
   • 对于每个输入的数字：
     • 检查之前的数字中是否有重复
     • 如果是第一次出现，则保留并输出
     • 如果已经出现过，则跳过
4. 复杂度分析：
   • 时间复杂度：$O(n^2)$
     • 外层循环遍历每个数字：$O(n)$
     • 内层循环检查重复：$O(n)$
   • 空间复杂度：$O(n)$，需要一个数组存储输入序列

---

示例代码

#include <iostream>

// 定义一个大小为20005的整型数组，用于存储输入的数字序列
// 初始化所有元素为0
// 数组大小设置为20005是为了确保能够容纳题目要求的最大输入规模(n≤20000)
int num_array[20005] = {};
int main() {
    // 读取输入的数字个数
    int n;
    std::cin >> n;
    
    // 遍历输入的每个数字
    for (int i = 0; i < n; i++) {
        // 读取当前数字
        int num;
        std::cin >> num;
        
        // 标记当前数字是否已经出现过
        bool flag = true;
        
        // 检查当前数字是否在之前的数组中出现过
        for (int j = 0; j < i; j++) {
            if (num_array[j] == num) {
                // 如果找到重复数字，设置标记为false并跳出循环
                flag = false;
                break;
            }
        }
        
        // 如果是第一次出现的数字，则输出并保存到数组中
        if (flag) {
            std::cout << num << " ";
            num_array[i] = num;
        }
    }
    return 0;
}

练习用vector实现

#include <iostream>
#include <vector>

// 用于存储不重复数字的向量
std::vector<int> num_array;
int main() {
    // 读取输入的数字个数
    int n;
    std::cin >> n;
    
    // 遍历输入的每个数字
    for (int i = 0; i < n; i++) {
        // 读取当前数字
        int num;
        std::cin >> num;
        
        // 标记当前数字是否为第一次出现
        bool flag = true;
        
        // 检查当前数字是否在向量中已经存在
        for (const int& v : num_array) {
            if (v == num) {
                // 如果找到重复数字，设置标记为false并跳出循环
                flag = false;
                break;
            }
        }
        
        // 如果是第一次出现的数字，则输出并添加到向量中
        if (flag) {
            std::cout << num << " ";
            num_array.push_back(num);
        }
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。