有学生对学校附近一些租房的价格进行了统计,现将这些价格数据存入一个数组arr,求数组arr中第k大的房租价格。请用C语言实现这一逻辑。
时间: 2024-02-15 22:04:42 浏览: 20
好的,根据您的需求,这里是一份 C 语言程序,它可以从标准输入中读取整数数组和 k 的值,并输出第 k 大的数。
```c
#include <stdio.h>
int partition(int arr[], int left, int right) {
int pivot = arr[left];
int i = left + 1, j = right;
while (i <= j) {
if (arr[i] < pivot && arr[j] > pivot) {
int temp = arr[i];
arr[i++] = arr[j];
arr[j--] = temp;
}
if (arr[i] >= pivot) {
i++;
}
if (arr[j] <= pivot) {
j--;
}
}
int temp = arr[j];
arr[j] = arr[left];
arr[left] = temp;
return j;
}
int quick_select(int arr[], int left, int right, int k) {
int pivot_index = partition(arr, left, right);
if (pivot_index == k - 1) {
return arr[pivot_index];
} else if (pivot_index > k - 1) {
return quick_select(arr, left, pivot_index - 1, k);
} else {
return quick_select(arr, pivot_index + 1, right, k);
}
}
int main() {
int n, arr[1000], k;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
scanf("%d", &k);
int kth_largest = quick_select(arr, 0, n - 1, k);
printf("%d\n", kth_largest);
return 0;
}
```
这个实现中,我们使用了快速选择算法来找到第 k 大的数。快速选择算法是基于快速排序的,但是只需要对数组的一部分执行快速排序,因此时间复杂度是 O(n)。在这个实现中,`partition` 函数用于分割数组,`quick_select` 函数使用分割后的结果来递归寻找第 k 大的数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)