顺序统计中值---无序找第k大/小值-创新互联

问题描述:无序找第k小的数?

创新互联于2013年开始,是专业互联网技术服务公司,拥有项目成都网站建设、成都网站设计网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元额济纳做网站,已为上家服务,为额济纳各地企业和个人服务,联系电话:18980820575

1、解法一

 先排好序,再找第k小个数;返回A[k-1];此解法的时间复杂度为:O(nlogn);

2、解法二

 情况一:k = 1 和 k = n 就是找数组的最小值和大值;

 情况二:找出中位数

3、找中位数(随机选择算法)

 利用快速排序的原理,一轮排序,有2种情况:

 if i = k-1;返回a[i];

 if i != k-1;左边/右边递归查找,时间复杂度为:O(n);

具体思想:

顺序统计中值---无序找第k大/小值

 分析:在大多数情况下的时间复杂度是:O(n);但是最坏情况,完全顺序下找第k = n-1大数,此时的时间复杂度是:O(n^2);

4、无序找第k小值

快排的升序实现思想,在加上递归查找;

 (1)、代码实现

#include

void findKSmall(int *a, int start, int end, int key);

void findKSmall(int *a, int start, int end, int key){
    int i = start;
    int j = end;
    int tmp = a[i];
//快排中的升序
    while(i < j){
        while(i < j && a[j] > tmp){
            j--;
        }
        if(i < j){
            a[i++] = a[j];
        }
        while(i < j && a[i] < tmp){
            i++;
        }
        if(i < j){
            a[j--] = a[i];
        }
    }
    a[i] = tmp;

    if(key-1 < i){
        findKSmall(a, 0, i-1, key);
    }else if(key-1 > i){
        findKSmall(a, i+1, end, key);
    }else{
        return;
    }
}

void main(void){
    int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10};
    int count = sizeof(a)/sizeof(int);
    int k;
    int i;

    printf("请输入要查找的第k小的数:");
    scanf("%d", &k);
    findKSmall(a, 0, count-1, k);
    for(i = 0; i < count; i++){
        printf("%d ", a[i]);
    }

    printf("\n%d\n", a[k-1]);

}

 结果截图

顺序统计中值---无序找第k大/小值

5、无序找第k大值

快排的降序实现思想,在加上递归查找;

(1)、代码实现

#include

void findKBigger(int *a, int start, int end, int key);

void findKBigger(int *a, int start, int end, int key){
    int i = start;
    int j = end;
    int tmp = a[i];
//快排中的降序
    while(i < j){
        while(i < j && a[j] < tmp){
            j--;
        }
        if(i < j){
            a[i++] = a[j];
        }
        while(i < j && a[i] > tmp){
            i++;
        }
        if(i < j){
            a[j--] = a[i];
        }
    }
    a[i] = tmp;

    if(key-1 < i){
        findKBigger(a, 0, i-1, key);
    }else if(key-1 > i){
        findKBigger(a, i+1, end, key);
    }else{
        return;
    }
}

void main(void){
    int a[] = {8, 4, 6, 9, 2, 3, 7, 9, 11, 10};
    int count = sizeof(a)/sizeof(int);
    int k;
    int i;

    printf("请输入要查找的第k大的数:");
    scanf("%d", &k);
    findKBigger(a, 0, count-1, k);
    for(i = 0; i < count; i++){
        printf("%d ", a[i]);
    }

    printf("\n%d\n", a[k-1]);

}

 (2)、结果截图

顺序统计中值---无序找第k大/小值

6、线性算法

 (1)、划分为5个一组的元素,在找出每一组的中值(对这5个数进行排序,找出中值),时间复杂度:O(n)

 (2)、用递归去找这些中值中的那一个中值(中值中的中值);

 (3)、此时用这个最中值的下标和k作比较,之后和上面的随机选择算法一样!!!

具体模型如下:

顺序统计中值---无序找第k大/小值

算法分析

 找中值和第k小数时间复杂度均为:O(n);比较好的解决了上述最坏时间复杂度为O(n^2)的情况;

 3个元素一组的话,结果不成立;

 5是这个算法能成功的最小数字,7个元素为一组算法也能成立,但是性能不会有所提高;

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网站题目:顺序统计中值---无序找第k大/小值-创新互联
分享URL:http://scyanting.com/article/cdshij.html