题解 | #集合#

#include <stdio.h>
#include <stdbool.h>

// 快速排序
void quickSort(int* arr, int left, int right) {
  if (left >= right) {
    return;
  }
  int pivot = arr[left];
  int i = left + 1, j = right;
  while (i <= j) {
    if (arr[i] > pivot && arr[j] < pivot) {
      // 交换 arr[i] 和 arr[j]
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
      i++;
      j--;
    } else if (arr[i] <= pivot) {
      i++;
    } else if (arr[j] >= pivot) {
      j--;
    }
  }
  // 交换 arr[left] 和 arr[j]
  arr[left] = arr[j];
  arr[j] = pivot;
  quickSort(arr, left, j - 1);
  quickSort(arr, j + 1, right);
}

void mergeSets(int* setA, int sizeA, int* setB, int sizeB) {
  // 对 A 和 B 集合执行快速排序
  quickSort(setA, 0, sizeA - 1);
  quickSort(setB, 0, sizeB - 1);

  int merged[sizeA + sizeB];
  int i = 0, j = 0, k = 0;

  while (i < sizeA && j < sizeB) {
    if (setA[i] < setB[j]) {
      merged[k++] = setA[i++];
    } else if (setA[i] > setB[j]) {
      merged[k++] = setB[j++];
    } else {
      merged[k++] = setA[i++];
      j++;
    }
  }

  while (i < sizeA) {
    merged[k++] = setA[i++];
  }

  while (j < sizeB) {
    merged[k++] = setB[j++];
  }

  for (int idx = 0; idx < k; idx++) {
    printf("%d ", merged[idx]);
  }
  printf("\n");
}

int main() {
  int n, m;
  while (scanf("%d %d", &n, &m) == 2) {
    int setA[n];
    int setB[m];

    for (int i = 0; i < n; i++) {
      scanf("%d", &setA[i]);
    }

    for (int i = 0; i < m; i++) {
      scanf("%d", &setB[i]);
    }

    mergeSets(setA, n, setB, m);
  }
  return 0;
}