P1059 [NOIP 2006 普及组] 明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 \(N\) 个 \(1\) 到 \(1000\) 之间的随机整数 \((N\leq100)\)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
输入有两行，第 \(1\) 行为 \(1\) 个正整数，表示所生成的随机数的个数 \(N\)。
第 \(2\) 行有 \(N\) 个用空格隔开的正整数，为所产生的随机数。
输出格式
输出也是两行，第 \(1\) 行为 \(1\) 个正整数 \(M\)，表示不相同的随机数的个数。
第 \(2\) 行为 \(M\) 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
NOIP 2006 普及组 第一题
Tip
好，这题是去重 + 排序（快排版），我继续按你模板来👇
📌 题目分析
👉 本质： 对数组进行：
👉 类型： 排序 + 去重
🧠 解题思路（快排版）
1️⃣ 核心建模
输入数组 a[i]
目标：
2️⃣ 方法选择
👉 两种常见思路：
方法一（推荐）
方法二
👉 本题要求：快排 → 用方法一
3️⃣ 算法流程
Step 1️⃣：快排
把数组排序：
Step 2️⃣：去重（关键）
用一个新数组 b[]
4️⃣ 举例
5️⃣ 时间复杂度
💻 C++代码（手写快排）
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N], b[N];
int n;
void quick_sort(int l, int r) {
if (l >= r) return;
int i = l, j = r;
int pivot = a[(l + r) >> 1];
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
swap(a[i], a[j]);
i++, j--;
}
}
if (l < j) quick_sort(l, j);
if (i < r) quick_sort(i, r);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
// 1️⃣ 快排
quick_sort(0, n - 1);
// 2️⃣ 去重
int m = 0;
b[m++] = a[0];
for (int i = 1; i < n; i++) {
if (a[i] != a[i - 1]) {
b[m++] = a[i];
}
}
// 输出
cout << m << "\n";
for (int i = 0; i < m; i++) {
cout << b[i] << " ";
}
return 0;
}
⚠️ 易错点
❌ 1. 忘记排序就去重
❌ 2. b数组初始化错误
❌ 3. 下标越界
✅ 正确：