A41062. 明明的随机数
填空题
困难
知识点
题目描述
明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
输入2行，第1行为1个正整数，表示所生成的随机数的个数：N
第2行有N个用空格隔开的正整数，为所产生的随机数。
输出格式
输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
样例输入
10
20 40 32 67 40 20 89 300 400 15
样例输出
8
15 20 32 40 67 89 300 400
参考答案
#include <iostream>
using namespace std;
void quickSort(int arr[], int start, int end); // 快速排序
void duplicateRemoval(int arr[], int len); // 去重并输出剩余元素个数
int main() {
int N = 0; // 随机数个数
cin >> N;
int arr[N] = { 0 }; // 存储随机数
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
quickSort(arr, 0, N - 1); // 先排序
duplicateRemoval(arr, N); // 后去重
for (int i = 0; i < N; i++) {
if (arr[i]) {
cout << arr[i] << " ";
}
}
return 0;
}
void quickSort(int arr[], int start, int end) {
// 这一步很关键，写成==都无法输出，因为到只剩1个元素时start == left，但传入参数为start和left - 1
if (start >= end) {
return;
}
int pivot = arr[start]; // 基准值
int left = start; // 从左向右遍历找比pivot大的数
int right = end; // 从右向左遍历找比pivot小的数
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--; // 找到比pivot小的数
}
if (left < right) {
arr[left] = arr[right]; // 移动到left位置，因为left的值已经传给pivot了
}
while (left < right && arr[left] <= pivot) {
left++; // 找到比pivot大的数
}
if (left < right) {
arr[right] = arr[left]; // 移动到right位置，因为right的值已经传给left了
}
}
arr[left] = pivot; // left和right相遇，把基准值放到这里，至此就实现了左边都比pivot小，右边都比pivot大
quickSort(arr, start, left - 1);
quickSort(arr, right + 1, end);
}
void duplicateRemoval(int arr[], int len) {
int count = len; // 剩余元素个数
for (int i = 0; i < len - 1; i++) {
if (arr[i] == arr[i + 1]) {
arr[i] = 0; // 由于题目要求随机数均为正整数，所以归零就算是去重了
count--;
}
}
cout << count << endl; // 输出剩余个数
}
上一题
下一题