请选择 进入手机版 | 继续访问电脑版
  • 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

线性时间复杂度求数组中第K大的数【原创】

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

求数组中第K大的数可以基于快排序思想,步骤如下:

1.随机选择一个支点

2.将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)

3.设左部分的长度为L,

当K < L时,递归地在左部分找第K大的数

当K > L时,递归地在有部分中找第(K – L)大的数

当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数

以上思想的代码实现如下:

 

 

#include <iostream>
using namespace std;

int selectk(int a[], int low, int high, int k)
{
    if(k <= 0) return -1;
    if(k > high - low + 1) return -1;
    int pivot = low + rand()%(high - low + 1);
    swap(a[low], a[pivot]);
    int m = low;
    int count = 1;

    //一趟遍历,把较大的数放到数组的左边

    for(int i = low + 1; i <= high; ++i)
    {
       if(a[i] > a[low])
       {
            swap(a[++m], a[i]);
            count++;
       }
    }
    swap(a[m], a[low]);
    if(count > k)
    {
        return selectk(a, low, m - 1, k);
    }
    else if( count < k)
    {
       return selectk(a, m + 1, high, k - count);
    }
    else
    {
       return m;
    }
}
int main(int argc, char** argv)
{
    /*1,1,1,1,1,1,1,1,3,5,5,7,9,10,10,12,15,16,17,18,19,100,1000*/
    int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
    int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 5);
    cout<<(r == -1 ? r : a[r])<<endl;
    system("pause");
    return 0;
}

鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
B树、B-树、B+树、B*树 介绍、比较与小结(转载)发布时间:2022-05-14
下一篇:
单链表的快速排序(原创)发布时间:2022-05-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap