使用O(n)的复杂度
时间: 2023-12-11 16:06:11 浏览: 37
如果要寻找最小的k个数并且要求使用O(n)的时间复杂度,可以使用快速选择算法。
快速选择算法的基本思想是类似于快速排序,但是只需要对一个子数组进行递归调用,而不是对两个子数组进行递归调用。具体实现方法是首先选定一个枢轴元素,然后将数组分为两个部分,一部分是小于枢轴元素的元素,另一部分是大于枢轴元素的元素。如果小于枢轴元素的元素的个数大于等于k,那么就在小于枢轴元素的元素中继续查找最小的k个数;否则,在大于枢轴元素的元素中查找剩下的最小的k-(小于枢轴元素的元素个数)个数。
以下是使用C语言实现的代码:
```c
#include<stdio.h>
#include<stdlib.h>
// 交换两个数的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 将数组分为两个部分,并返回枢轴元素的位置
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low + 1;
int j = high;
while (i <= j) {
if (arr[i] <= pivot) {
i++;
}
else if (arr[j] > pivot) {
j--;
}
else {
swap(&arr[i], &arr[j]);
}
}
swap(&arr[low], &arr[j]);
return j;
}
// 寻找最小的k个数
void find_k_min(int arr[], int n, int k) {
int low = 0;
int high = n - 1;
while (low <= high) {
int pivotIndex = partition(arr, low, high);
if (pivotIndex == k - 1) {
// 输出最小的k个数
printf("最小的%d个数为:", k);
for (int i = 0; i < k; i++) {
printf("%d ", arr[i]);
}
return;
}
else if (pivotIndex > k - 1) {
high = pivotIndex - 1;
}
else {
low = pivotIndex + 1;
}
}
}
int main() {
int arr[] = { 3, 6, 1, 9, 7, 2, 8, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
find_k_min(arr, n, k);
return 0;
}
```
以上代码的时间复杂度为O(n),其中n为数组长度,k为要寻找的最小数的个数。