合并两个数组并排序去重

数组并排序去重"/>

合并两个数组并排序去重

题目：        

        给定2个数组，要求把他们合并成1个非降序序列，并且输出去重后的序列。

输入格式:

        输入有4行。
        第1行是一个正整数m，表示第2行有m个整数，这些整数构成一个非降序序列，每个整数之间以空格隔开。第3行是一个正整数n，表示第4行有n个整数，这些整数也构成一个非降序序列，每个整数之间以空格隔开。

输出格式:

        把第2行的m个整数和第4行的n个整数合并成一个非降序序列，输出这个整数序列。每个数之间隔1个空格。

输入样例:

6
1 3 6 6 8 9
4
4 2 1 4 5 7

输出样例：

1 2 3 4 6 8 9

代码限制：

代码长度限制：16 KB

时间限制：100 ms

内存限制：64 MB

代码：

#include <stdio.h>// 交换函数
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 快速排序
void quick_sort(int q[], int l, int r) {if (l >= r)return;int i = l - 1, j = r + 1, x = q[(l + r) >> 1];while (i < j) {doi++;while (q[i] < x);doj--;while (q[j] > x);if (i < j)swap(&q[i], &q[j]);}quick_sort(q, l, j);quick_sort(q, j + 1, r);
}// 双“指针”遍历去重
int removeDuplicates(int *arr, int count) {int slow = 0, fast = 1;while (fast < count) {if (arr[fast] != arr[slow]) {slow = slow + 1;arr[slow] = arr[fast];}fast = fast + 1;}return slow + 1;//返回新数组的长度
}int main() {// 输入第一个有序数组int num_arr1 = 0;scanf("%d", &num_arr1);int arr1[num_arr1];for (int i = 0; i < num_arr1; i++) {scanf("%d", &arr1[i]);}// 输入第二个有序数组int num_arr2 = 0;scanf("%d", &num_arr2);int arr2[num_arr2];for (int i = 0; i < num_arr2; i++) {scanf("%d", &arr2[i]);}// 将两个数组合并再排序int num_arr3 = num_arr1 + num_arr2;int arr3[num_arr3];// 将arr1赋值给arr3for (int i = 0; i < num_arr1; i++) {arr3[i] = arr1[i];}// 将arr2赋值给arr3for (int i = 0; i < num_arr2; i++) {arr3[i + num_arr1] = arr2[i];}// 对arr3进行排序并输出结果quick_sort(arr3, 0, num_arr3 - 1);// 去除重复元素int num_Duplicates = removeDuplicates(arr3, num_arr3);for (int i = 0; i < num_Duplicates; i++) {printf("%d", arr3[i]);printf(" ");}
}