题目 2913: 整数去重 时间限制: 1s 内存限制: 128MB 提交: 90 解决: 37 题目描述 给定含有n个整数的序列,要求对这个序列进行去重操作。所谓去重,是指对这个序列中每个重复出现的...
时间: 2024-03-10 16:47:27 浏览: 26
这是一道比较简单的题目,可以使用set来进行去重操作。set是C++中的一个容器,可以自动去重并且按照从小到大的顺序排序。具体实现代码如下:
```c++
#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
s.insert(x); // 将整数插入set中
}
for (auto it = s.begin(); it != s.end(); it++) {
cout << *it << " "; // 遍历set并输出去重后的整数序列
}
return 0;
}
```
其中,set<int> s;声明了一个名为s的set容器,存储整数类型的数据。在输入整数序列时,每输入一个整数x,即可使用s.insert(x);将整数插入set中,set会自动去重。最后,使用auto关键字遍历set容器,并输出去重后的整数序列。
相关问题
id:313】【20分】B. 冒泡排序 时间限制 1s 内存限制 128MB 题目描述 给定一个包含从0到n-1各一次的数组,若使用冒泡排序将其排为升序,问其中需要进行多少次交换 输入 测试数据有多组, 每组由两行组成:第一行包含正整数n(n <= 5000); 下一行包含从0到n-1的n个整数的序列。 输出 对于每组测试数据, 输出交换次数
以下是一种冒泡排序的实现方式,可以记录每次交换的次数:
```c++
#include <iostream>
using namespace std;
int main() {
int n;
while (cin >> n) {
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int swaps = 0;
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
swaps++;
}
}
}
cout << swaps << endl;
}
return 0;
}
```
对于每组测试数据,先读入数组,然后使用双重循环进行冒泡排序,并记录每次交换的次数。最后输出交换次数即可。
2路归并排序 时间限制 1s 内存限制 128MB 题目描述 给定一组正整数序列,执行2路归并排序算法得到由小到大的序列。要求按2路归并排序树,自下而上自左向右的次序,输出每个有序的子序列。 输入 第1行该序列的正整数个数n 第2行n个正整数,元素之间由空格分开 输出 m:表示2路归并排序树的结点个数 m行,每行是有序的子序列 样例查看模式 正常显示 查看格式 输入样例1 <-复制 5 23 38 17 16 25 输出样例1 9 23 38 23 38 17 16 25 17 23 38 16 25 16 17 23 25 38 语言: C++
以下是C++的代码实现,其中使用了归并排序算法,具体实现过程中,使用了递归和迭代两种方式实现归并排序。对于每次归并排序,输出有序子序列,直到整个序列有序。
```c++
#include <iostream>
#include <vector>
using namespace std;
// 归并排序算法
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return; // 直到只剩下一个元素
int mid = (left + right) / 2;
mergeSort(nums, left, mid); // 左半部分归并排序
mergeSort(nums, mid + 1, right); // 右半部分归并排序
// 归并两个有序子序列
vector<int> temp;
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp.push_back(nums[i++]);
} else {
temp.push_back(nums[j++]);
}
}
while (i <= mid) temp.push_back(nums[i++]);
while (j <= right) temp.push_back(nums[j++]);
// 将归并结果复制回原数组中
for (int k = left; k <= right; k++) {
nums[k] = temp[k - left];
}
// 输出当前有序子序列
cout << right - left + 1 << " ";
for (int k = left; k <= right; k++) {
cout << nums[k] << " ";
}
cout << endl;
}
// 归并排序算法(迭代版本)
void mergeSortIter(vector<int>& nums) {
int n = nums.size();
for (int len = 1; len < n; len *= 2) {
for (int i = 0; i < n - len; i += 2 * len) {
int left = i, mid = i + len - 1, right = min(i + 2 * len - 1, n - 1);
// 归并两个有序子序列
vector<int> temp;
int j = left, k = mid + 1;
while (j <= mid && k <= right) {
if (nums[j] <= nums[k]) {
temp.push_back(nums[j++]);
} else {
temp.push_back(nums[k++]);
}
}
while (j <= mid) temp.push_back(nums[j++]);
while (k <= right) temp.push_back(nums[k++]);
// 将归并结果复制回原数组中
for (int p = left; p <= right; p++) {
nums[p] = temp[p - left];
}
// 输出当前有序子序列
cout << right - left + 1 << " ";
for (int p = left; p <= right; p++) {
cout << nums[p] << " ";
}
cout << endl;
}
}
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
// 归并排序算法
//mergeSort(nums, 0, n - 1);
// 归并排序算法(迭代版本)
mergeSortIter(nums);
return 0;
}
```
其中,`mergeSort`函数使用递归方式实现归并排序,`mergeSortIter`函数使用迭代方式实现归并排序。两个函数的时间复杂度都是$O(n\log n)$,空间复杂度都是$O(n)$,其中$n$是序列中元素的个数。