C语言给定n个元素和一个整数k,要求用O(n)时间找出这n个元素中第k小元素。编写代码。
时间: 2024-10-18 10:21:24 浏览: 13
C语言程序设计-找出一个大于给定整数且紧随这个整数的素数,并作为函数值返回;
5星 · 资源好评率100%
在C语言中,找到一个数组中第k小的元素可以使用一种叫做“快速选择”(QuickSelect)算法的优化版本,它基于分治策略,平均时间复杂度可以达到O(n),但在最坏的情况下是O(n^2)。下面是一个简单的示例,假设数组已经排序:
```c
#include <stdio.h>
#include <stdlib.h>
// 交换两个元素
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 快速选择的辅助函数
int partition(int arr[], int low, int high, int pivot_index) {
int pivot = arr[pivot_index];
swap(&arr[low], &arr[pivot_index]); // 将pivot放到最低位
int i = (low - 1); // index of smaller element
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[low]); // 将pivot放到正确的位置
return i + 1;
}
// 快速选择
int quickselect(int arr[], int low, int high, int k) {
if (low == high) { // base case: single element array
return arr[low];
}
int pivot_index = partition(arr, low, high, rand() % (high - low + 1)); // 随机选择一个分割点
if (k == pivot_index) {
return arr[k]; // 如果正好命中,则返回
} else if (k < pivot_index) {
return quickselect(arr, low, pivot_index - 1, k); // 递归处理左半部分
} else {
return quickselect(arr, pivot_index + 1, high, k); // 递归处理右半部分
}
}
int main() {
int n, k;
printf("Enter the number of elements: ");
scanf("%d", &n);
int* arr = malloc(n * sizeof(int));
printf("Enter the elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the value of k: ");
scanf("%d", &k);
int kth_smallest = quickselect(arr, 0, n - 1, k - 1); // 函数索引减1是因为从0开始计数
printf("The kth smallest element is: %d\n", kth_smallest);
free(arr);
return 0;
}
```
这个程序首先读取输入的元素、数组长度以及需要查找的k值,然后利用快速选择算法找到第k小的元素。
阅读全文