有10个互不相同的整数:99、200、95、87、98、-12、30、87、75、-25,不用排序,每当输入一个1-10之间的数n,即可输出第n个大的数。比如,输入2,则输出99. 请设计并实现一算法,传入数字n即可输出第n个大的数用。C语言结论
时间: 2024-05-22 21:13:52 浏览: 7
我可以帮你实现这个算法。我的建议是使用快速选择算法。首先,将这10个数字随机分为两组,一组比第一个数字小,另一组比第一个数字大。然后,比较第n个大的数字与第一个数字的大小。如果第n个大的数字比第一个数字大,则在大数字组中继续使用快速选择算法进行查找;否则,在小数字组中继续查找。重复这个过程,直到找到第n个大的数字为止。下面是C语言代码实现:
#include <stdio.h>
int partition(int arr[], int left, int right) {
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] < pivot)
j--;
while (i < j && arr[i] >= pivot)
i++;
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
int quickSelect(int arr[], int left, int right, int nth) {
int pivotIndex = partition(arr, left, right);
int rank = pivotIndex - left + 1;
if (rank == nth) {
return arr[pivotIndex];
} else if (rank > nth) {
return quickSelect(arr, left, pivotIndex - 1, nth);
} else {
return quickSelect(arr, pivotIndex + 1, right, nth - rank);
}
}
int main() {
int arr[] = {99, 200, 95, 87, 98, -12, 30, 87, 75, -25};
int n;
printf("请输入n:");
scanf("%d", &n);
printf("第%d个大的数是:%d\n", n, quickSelect(arr, 0, 9, n));
return 0;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)