luogu-B2098 整数去重

luogu-B2098 整数去重

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

luogu-B2098 整数去重

题目要求

题目描述

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

输入格式

输入包含两行:

第一行包含一个正整数 nn1n200001 \le n \le 20000),表示第二行序列中数字的个数;

第二行包含 nn 个整数,整数之间以一个空格分开。每个整数大于等于 1010 、小于等于 100100

输出格式

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

输入输出样例 #1

输入 #1

5
10 12 93 12 75

输出 #1

10 12 93 75

题目分析

解题思路

本题的解题思路如下:

  1. 问题本质:

    • 对输入的数字序列进行去重
    • 保留每个数字第一次出现的位置
  2. 解题关键:

    • 遍历输入序列中的每个数字
    • 检查当前数字是否已经出现过
    • 只保留第一次出现的数字
  3. 实现思路:

    • 使用一个数组存储输入的序列
    • 对于每个输入的数字:
      • 检查之前的数字中是否有重复
      • 如果是第一次出现,则保留并输出
      • 如果已经出现过,则跳过
  4. 复杂度分析:

    • 时间复杂度:O(n2)O(n^2)
      • 外层循环遍历每个数字:O(n)O(n)
      • 内层循环检查重复:O(n)O(n)
    • 空间复杂度:O(n)O(n),需要一个数组存储输入序列

{% include custom/custom-post-content-inner.html %}


示例代码

#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;
}

{% include custom/custom-post-content-footer.md %}

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

luogu-”系列题目可在 洛谷题库 在线评测。

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

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
Last updated on