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

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 语言实现的快速选择算法示例：

#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; j++) {
        if (arr[j] > pivot) {
            i++;
            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 quick_select(int arr[], int low, int high, int K) {
    if (low == high) {
        return arr[low];
    }

    int pivot_index = partition(arr, low, high);
    if (K == pivot_index) {
        return arr[K];
    } else if (K < pivot_index) {
        return quick_select(arr, low, pivot_index - 1, K);
    } else {
        return quick_select(arr, pivot_index + 1, high, K);
    }
}

int main() {
    long long N, K, i;
    scanf("%lld", &N);
    int a[N];
    scanf("%lld", &K);
    for (i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }

    int result = quick_select(a, 0, N - 1, K - 1);
    printf("%d\n", result);

    return 0;
}

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

跳转到最佳答案楼层

isdkz

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

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

以下是使用 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; j++) {
        if (arr[j] > pivot) {
            i++;
            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 quick_select(int arr[], int low, int high, int K) {
    if (low == high) {
        return arr[low];
    }

    int pivot_index = partition(arr, low, high);
    if (K == pivot_index) {
        return arr[K];
    } else if (K < pivot_index) {
        return quick_select(arr, low, pivot_index - 1, K);
    } else {
        return quick_select(arr, pivot_index + 1, high, K);
    }
}

int main() {
    long long N, K, i;
    scanf("%lld", &N);
    int a[N];
    scanf("%lld", &K);
    for (i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }

    int result = quick_select(a, 0, N - 1, K - 1);
    printf("%d\n", result);

    return 0;
}

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