C语言输入未知个数整数,输出其中最小的k个
时间: 2024-01-22 08:19:33 浏览: 27
可以使用堆排序来解决这个问题。首先,我们可以定义一个大小为k的最大堆,然后每输入一个整数,就将它与堆顶元素进行比较,如果小于堆顶元素,则将堆顶元素替换为该整数,并重新调整堆,以保证堆中仍然只有k个元素且堆顶元素为最大值。最终,堆中剩余的k个元素就是输入中最小的k个整数。
以下是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void max_heapify(int arr[], int heap_size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heap_size && arr[left] > arr[largest]) {
largest = left;
}
if (right < heap_size && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(&arr[i], &arr[largest]);
max_heapify(arr, heap_size, largest);
}
}
void build_max_heap(int arr[], int heap_size) {
for (int i = heap_size / 2 - 1; i >= 0; i--) {
max_heapify(arr, heap_size, i);
}
}
void heap_sort(int arr[], int heap_size) {
build_max_heap(arr, heap_size);
for (int i = heap_size - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, i, 0);
}
}
void print_min_k(int arr[], int n, int k) {
int heap[MAX_HEAP_SIZE];
int heap_size = 0;
for (int i = 0; i < n; i++) {
if (heap_size < k) {
heap[heap_size++] = arr[i];
if (heap_size == k) {
build_max_heap(heap, heap_size);
}
} else {
if (arr[i] < heap[0]) {
heap[0] = arr[i];
max_heapify(heap, heap_size, 0);
}
}
}
heap_sort(heap, heap_size);
printf("The smallest %d numbers are: ", k);
for (int i = 0; i < k; i++) {
printf("%d ", heap[i]);
}
printf("\n");
}
int main() {
int arr[MAX_HEAP_SIZE];
int n, k;
printf("Please enter the number of integers: ");
scanf("%d", &n);
printf("Please enter the integers: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Please enter k: ");
scanf("%d", &k);
print_min_k(arr, n, k);
return 0;
}
```
这个代码的时间复杂度为O(nlogk),其中n为输入整数的个数,k为最小的k个整数的个数。