用c++写出一下题目代码及其注释及其算法思想:有T组数据。 每组数据给定长度为 N的数组 A,对所有长度大于等于 k 的连续子段,取出其第 k 大放入数组 B 中。求数组 B 的第 M 大
时间: 2024-05-21 08:11:24 浏览: 56
#include <stdio.h>
#include <stdlib.h>
// 快速排序
void quick_sort(int *arr, int left, int right) {
if (left >= right) return;
int i = left, j = right, pivot = arr[left];
while (i < j) {
while (i < j && arr[j] <= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] >= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
quick_sort(arr, left, i - 1);
quick_sort(arr, i + 1, right);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int N, k, M;
scanf("%d%d%d", &N, &k, &M);
int *A = (int*)malloc(N * sizeof(int));
int cnt = 0;
for (int i = 0; i < N; i++) {
scanf("%d", &A[i]);
if (i >= k - 1) cnt++;
}
int *B = (int*)malloc(cnt * sizeof(int));
cnt = 0;
for (int i = 0; i < N - k + 1; i++) {
int *tmp = (int*)malloc(k * sizeof(int));
for (int j = 0; j < k; j++) {
tmp[j] = A[i + j];
}
quick_sort(tmp, 0, k - 1);
B[cnt++] = tmp[k - 1];
free(tmp);
}
quick_sort(B, 0, cnt - 1); // 对数组B进行排序
printf("%d\n", B[cnt - M]); // 输出数组B的第M大
free(A);
free(B);
}
return 0;
}
// 算法思想:
// 1. 读入T组数据
// 2. 对于每组数据,读入N、k、M和数组A
// 3. 遍历数组A,对每个长度大于等于k的连续子段取出其第k大,并放入数组B中
// 4. 对数组B进行排序
// 5. 输出数组B的第M大
阅读全文