鱼C论坛

 找回密码
 立即注册
查看: 1602|回复: 1

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

[复制链接]
发表于 2023-3-17 20:33:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
求 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;
}
最佳答案
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 大的数。这种方法的性能会优于冒泡排序,尤其是在处理大量数据时。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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 大的数。这种方法的性能会优于冒泡排序,尤其是在处理大量数据时。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 11:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表