题目一:线性时间选择 给定n个元素和一个整数k,要求用O(n)时间找出这n个元素中第k小元素。用C语言代码
时间: 2024-10-18 09:21:28 浏览: 7
线性时间选择(Linear Time Selection)是指在平均和最坏情况下,算法能在时间复杂度为 O(n) 内找到一个数组中第 k 小的元素。这通常使用分治策略中的“快速选择”(Quickselect)算法实现,而不是完全排序整个数组。
下面是使用 C 语言实现的一个简单版本的快速选择算法:
```c
#include <stdio.h>
#include <stdlib.h>
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 小于基准的元素索引
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将基准放到正确的位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
int quickSelect(int arr[], int low, int high, int k) {
if (low == high) { // 基准只有一个时直接返回
return arr[low];
}
int pivot_index = partition(arr, low, high);
// 如果 k 等于基准位置,则找到第 k 小的元素
if (k == pivot_index)
return arr[k];
else if (k < pivot_index) // 第 k 小的元素在左半边
return quickSelect(arr, low, pivot_index - 1, k);
else // 第 k 小的元素在右半边
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 %d numbers: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
scanf("Enter k: %d", &k);
if (k > 0 && k <= n) {
int kth_smallest = quickSelect(arr, 0, n - 1, k - 1); // 注意索引从0开始计数
printf("The k-th smallest element is: %d\n", kth_smallest);
} else {
printf("Invalid input for k.\n");
}
free(arr);
return 0;
}
```
这个程序首先读取元素并分配内存,然后调用 `quickSelect` 函数找到第 k 小的元素。当输入的 k 不在有效范围内时,程序会显示错误信息。
阅读全文