[已解决]运行超时，怎么改进

giegie666

求 n 个整数中第 k(1≤k≤n) 大的整数。

输入格式
n 和 k
n 个整数

输出格式
第 k 大的整数









#include <stdio.h>
#include <stdlib.h>
int main()
{
    long long N,K,i;
    scanf("%lld",&N); //输入数的个数
    int a[N];
    scanf("%lld",&K); //确定一个第K大的数
    for(i=0;i<N;i++){
        scanf("%lld",&a[i]);
    } //为数组输入变量
    int temp,j,m;
    for(j=0;j<N-1;j++){
        for(m=0;m<N-1-j;m++){
            if(a[m]<a[m+1]){
                temp=a[m];
                a[m]=a[m+1];
                a[m+1]=temp;
            }
        }
    } //降序冒泡排序
    printf("%lld",a[K-1]); //输出第K大的数
    return 0;
}

最佳答案

月排行榜 / 总排行榜

isdkz

2023-3-17 20:37:59

你的代码使用了冒泡排序算法，当处理大量数据时，可能导致运行超时。可以考虑使用更高效的排序算法，如快速排序（Quick Sort）或堆排序（Heap Sort）

你也可以尝试使用快速选择算法（Quick Select）来提高程序效率。快速选择算法是在快速排序算法的基础上修改而来的，用于在未排序的序列中查找第 k 大的元素，其平均时间复杂度为 O(n)。

以下是使用 C 语言实现的快速选择算法示例：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int partition(int arr[], int low, int high) {
   
5.     int pivot = arr[high];
   
6.     int i = low - 1;
   
7.     for (int j = low; j < high; j++) {
   
8.         if (arr[j] > pivot) {
   
9.             i++;
   
10.             int temp = arr[i];
    
11.             arr[i] = arr[j];
    
12.             arr[j] = temp;
    
13.         }
    
14.     }
    
15.     int temp = arr[i + 1];
    
16.     arr[i + 1] = arr[high];
    
17.     arr[high] = temp;
    
18.     return i + 1;
    
19. }
    
20. 
    
21. int quick_select(int arr[], int low, int high, int K) {
    
22.     if (low == high) {
    
23.         return arr[low];
    
24.     }
    
25. 
    
26.     int pivot_index = partition(arr, low, high);
    
27.     if (K == pivot_index) {
    
28.         return arr[K];
    
29.     } else if (K < pivot_index) {
    
30.         return quick_select(arr, low, pivot_index - 1, K);
    
31.     } else {
    
32.         return quick_select(arr, pivot_index + 1, high, K);
    
33.     }
    
34. }
    
35. 
    
36. int main() {
    
37.     long long N, K, i;
    
38.     scanf("%lld", &N);
    
39.     int a[N];
    
40.     scanf("%lld", &K);
    
41.     for (i = 0; i < N; i++) {
    
42.         scanf("%d", &a[i]);
    
43.     }
    
44. 
    
45.     int result = quick_select(a, 0, N - 1, K - 1);
    
46.     printf("%d\n", result);
    
47. 
    
48.     return 0;
    
49. }

复制代码

这段代码使用了快速选择算法来查找数组中第 K 大的数。这种方法的性能会优于冒泡排序，尤其是在处理大量数据时。

跳转到最佳答案楼层

isdkz

你的代码使用了冒泡排序算法，当处理大量数据时，可能导致运行超时。可以考虑使用更高效的排序算法，如快速排序（Quick Sort）或堆排序（Heap Sort）

你也可以尝试使用快速选择算法（Quick Select）来提高程序效率。快速选择算法是在快速排序算法的基础上修改而来的，用于在未排序的序列中查找第 k 大的元素，其平均时间复杂度为 O(n)。

以下是使用 C 语言实现的快速选择算法示例：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int partition(int arr[], int low, int high) {
   
5.     int pivot = arr[high];
   
6.     int i = low - 1;
   
7.     for (int j = low; j < high; j++) {
   
8.         if (arr[j] > pivot) {
   
9.             i++;
   
10.             int temp = arr[i];
    
11.             arr[i] = arr[j];
    
12.             arr[j] = temp;
    
13.         }
    
14.     }
    
15.     int temp = arr[i + 1];
    
16.     arr[i + 1] = arr[high];
    
17.     arr[high] = temp;
    
18.     return i + 1;
    
19. }
    
20. 
    
21. int quick_select(int arr[], int low, int high, int K) {
    
22.     if (low == high) {
    
23.         return arr[low];
    
24.     }
    
25. 
    
26.     int pivot_index = partition(arr, low, high);
    
27.     if (K == pivot_index) {
    
28.         return arr[K];
    
29.     } else if (K < pivot_index) {
    
30.         return quick_select(arr, low, pivot_index - 1, K);
    
31.     } else {
    
32.         return quick_select(arr, pivot_index + 1, high, K);
    
33.     }
    
34. }
    
35. 
    
36. int main() {
    
37.     long long N, K, i;
    
38.     scanf("%lld", &N);
    
39.     int a[N];
    
40.     scanf("%lld", &K);
    
41.     for (i = 0; i < N; i++) {
    
42.         scanf("%d", &a[i]);
    
43.     }
    
44. 
    
45.     int result = quick_select(a, 0, N - 1, K - 1);
    
46.     printf("%d\n", result);
    
47. 
    
48.     return 0;
    
49. }

复制代码

这段代码使用了快速选择算法来查找数组中第 K 大的数。这种方法的性能会优于冒泡排序，尤其是在处理大量数据时。