解题思路:
去重:数组的去重是很难直接把重复值“删去”的,此题要求输入的随机数都是正整数,所以可以把重复值全改成0,最后输出非0数,就算去重了。
先排序,后去重。排序使用快速排序。
注意事项:
快速排序函数中,判断结束的标志是start >= end,不能写成start == end,debug时在这里卡了很久。
参考代码:
// 题目 1102: 明明的随机数
#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; // 输出剩余个数
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:849 |
【偶数求和】 (C语言代码)浏览:556 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:653 |
printf基础练习2 (C语言代码)浏览:616 |
1011题解浏览:757 |
P1000 (C语言代码)浏览:867 |
出圈】指针malloc版浏览:355 |
数字游戏 (C++代码)浏览:1173 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:462 |
【计算直线的交点数】 (C语言代码)浏览:915 |