牛客网刷题 | BC125 序列中整数去重

目前主要分为三个专栏，后续还会添加：

专栏如下： C语言刷题解析 C语言系列文章我的成长经历

感谢阅读！

初来乍到，如有错误请指出，感谢！

描述

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

输入描述：

输入包含两行，第一行包含一个正整数n（1 ≤ n ≤ 1000），表示第二行序列中数字的个数；第二行包含n个整数（范围1~5000），用空格分隔。

输出描述：

输出为一行，按照输入的顺序输出去重之后的数字，用空格分隔。

为了实现去重并按顺序输出的功能，我们可以采用以下算法：

读取输入：
- 首先读取整数 n。
- 然后读取 n 个整数存储在一个数组中。
去重逻辑：
- 使用一个辅助数据结构来记录已经遇到的数字。
- 遍历数组中的每个数字，如果该数字尚未被记录，则将其添加到结果列表中，并标记为已处理。
输出结果：
- 按照原始顺序输出结果列表中的数字。

选择合适的数据结构

对于去重操作，可以选择使用一个布尔数组或哈希表来记录已经遇到的数字。由于题目中提到整数范围在1到5000之间，使用布尔数组是最简单且高效的选择。

布尔数组：
- 创建一个大小为5001的布尔数组 seen，初始值为 false。
- 对于每个读取到的数字 x，检查 seen[x] 是否为 false。
- 如果是 false，则将该数字添加到结果列表中，并将 seen[x] 设置为 true。

实现算法

根据上述设计，我们可以编写如下代码：

#include <stdio.h>
#include <stdbool.h>int main() {int n;scanf("%d", &n);int arr[n];bool seen[5001] = {false}; // 用于记录每个数字是否出现过for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}for (int i = 0; i < n; i++) {if (!seen[arr[i]]) {printf("%d ", arr[i]);seen[arr[i]] = true;}}return 0;
}

验证输出

最后，我们需要验证输出结果是否正确。通过上述步骤，我们已经实现了去重并按顺序输出的功能。让我们通过一些示例来验证我们的算法：

示例 1：

输入：

5
1 2 3 2 1

输出：

1 2 3

解释：

数字 1 和 2 出现了两次，但只输出一次。
数字 3 只出现了一次，直接输出。

示例 2：

输入：

7
10 20 30 40 50 60 70

输出：

10 20 30 40 50 60 70

解释：

所有数字都不同，直接输出。

错误示例

输入描述：

输入包含两行。
第一行包含一个正整数 n（1 ≤ n ≤ 1000），表示第二行序列中数字的个数。
第二行包含 n 个整数（范围1~5000），用空格分隔。

输出描述：

输出为一行，按照输入的顺序输出去重之后的数字，用空格分隔。

原始代码分析

原始代码存在以下几个问题：

输入部分：只读取了一个整数 a，但没有读取后续的 a 个整数。
去重逻辑：逻辑不正确，无法实现去重功能。
输出部分：输出方式不当，不能正确输出去重后的数字。

以下是原始代码：

#include <stdio.h>int main() {int a, b, i, arr[50] = {0};scanf("%d", &a);for (i = 0; i < a; i++){printf("%d", arr[i]);}for(int i = 0;i < a;i++){int c = arr[0];c++;if(c++ == arr[i]){arr[i] = 0;}}if(arr[i] != 0){printf("%d ",arr[i]);}return 0;
}

错误分析

输入部分：
- 问题：代码只读取了一个整数 a，表示数组长度，但没有读取后续的 a 个整数。
- 原因：缺少读取输入数字的循环。
- 影响：数组 arr 中的所有元素都是默认初始化的 0，而不是实际输入的数字。
去重逻辑：
- 问题：去重逻辑不正确，无法实现去重功能。
- 原因：
  - 变量 c 被初始化为 arr[0]，即 0。
  - c++ 和 if(c++ == arr[i]) 的逻辑混乱，导致无法正确识别和标记重复的数字。
  - 即使 c 能够正确递增，条件判断也不正确。
- 影响：数组中的元素没有被正确地去重。
输出部分：
- 问题：输出方式不当，不能正确输出去重后的数字。
- 原因：
  - 在第一个 for 循环中，直接输出了未初始化的数组元素（全部为 0）。
  - 第二个 for 循环结束后，i 已经超出数组范围，arr[i] 是无效的。
  - 最后一个 if 条件检查的是无效的数组索引，可能导致未定义行为。
- 影响：输出结果不符合题目要求，可能包含不必要的 0 或其他无效数据。

具体错误点

缺少读取输入数字的循环：

for (i = 0; i < a; i++) {printf("%d", arr[i]);
}

这段代码只是简单地打印了数组 arr 中的初始值（全部为 0），并没有从标准输入读取实际的数字。

去重逻辑错误：

for(int i = 0; i < a; i++) {int c = arr[0];c++;if(c++ == arr[i]) {arr[i] = 0;}
}

变量 c 初始化为 arr[0]：c 被初始化为 0，并且在每次循环中都被重新赋值为 0。

c++ 和 if(c++ == arr[i]) 的逻辑混乱：
- c++ 首先返回 c 的当前值，然后自增。
- if(c++ == arr[i]) 意味着 c 的当前值等于 arr[i] 时，c 自增一次，然后与 arr[i] 比较。这种逻辑会导致 c 的值不断变化，无法正确识别和标记重复的数字。
arr[i] = 0 的作用：即使 c 能够正确递增，条件判断也不正确，因此这个操作也不会达到预期的效果。

输出部分错误：

if(arr[i] != 0) {printf("%d ", arr[i]);
}

输出部分错误：

if(arr[i] != 0) {printf("%d ", arr[i]);
}

i 已经超出数组范围：第二个 for 循环结束后，i 的值为 a，超出了数组的有效索引范围 [0, a-1]。
arr[i] 是无效的：访问越界内存可能导致未定义行为或程序崩溃。
最后一个 if 条件检查无效：由于 i 超出范围，arr[i] 不是一个有效的数组元素，因此这个条件检查没有任何意义。

总结

通过上述分析，我们可以看到原始代码存在多个严重的问题：

缺少读取输入数字的循环。
去重逻辑混乱且不正确。
输出部分存在越界访问和无效条件检查。

步骤 1：正确读取输入

首先，我们需要正确读取输入的 n 个整数。这可以通过一个循环来实现。

#include <stdio.h>int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]); // 读取输入的数字}// 后续处理...return 0;
}

步骤 2：实现去重逻辑

我们需要遍历数组，对于每个未被标记为已处理过的元素，打印出来，并将所有相同的后续元素标记为已处理。

我们可以使用一个简单的标记方法：将已经处理过的元素标记为 -1。

#include <stdio.h>int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]); // 读取输入的数字}for (int i = 0; i < n; i++) {if (arr[i] != -1) { // 检查是否已经处理过printf("%d ", arr[i]);for (int j = i + 1; j < n; j++) {if (arr[j] == arr[i]) {arr[j] = -1; // 标记重复的数字}}}}return 0;
}

步骤 3：验证输出

最后，我们需要确保输出结果是正确的。通过上述步骤，我们已经实现了去重并按顺序输出的功能。

#include <stdio.h>int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]); // 读取输入的数字}for (int i = 0; i < n; i++) {if (arr[i] != -1) { // 检查是否已经处理过printf("%d ", arr[i]);for (int j = i + 1; j < n; j++) {if (arr[j] == arr[i]) {arr[j] = -1; // 标记重复的数字}}}}return 0;
}

更多方法

读取输入：
- 首先读取整数 n。
- 然后读取 n 个整数存储在一个数组中。
去重逻辑：
- 使用一个简单的标记方法来记录已经处理过的数字。
- 遍历数组中的每个数字，如果该数字尚未被标记，则将其添加到结果列表中，并标记为已处理。
输出结果：
- 按照原始顺序输出结果列表中的数字。

选择合适的数据结构

对于去重操作，可以选择使用一个布尔数组或哈希表来记录已经遇到的数字。然而，在本例中，我们选择了更简单的方法——使用数组元素自身的值来进行标记。具体来说，我们将重复的数字标记为 -1。

#include <stdio.h>int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]); // 读取输入的数字}for (int i = 0; i < n; i++) {if (arr[i] != -1) { // 检查是否已经处理过printf("%d ", arr[i]);for (int j = i + 1; j < n; j++) {if (arr[j] == arr[i]) {arr[j] = -1; // 标记重复的数字}}}}return 0;
}

去重逻辑

for (int i = 0; i < n; i++) {if (arr[i] != -1) { // 检查是否已经处理过printf("%d ", arr[i]);for (int j = i + 1; j < n; j++) {if (arr[j] == arr[i]) {arr[j] = -1; // 标记重复的数字}}}
}

外层循环 for (int i = 0; i < n; i++) 遍历数组中的每个元素。