现在的位置: 首页 > 自动控制 > 工业·编程 > 正文

线性时间复杂度求数组中第K大数

2012-08-23 23:57 工业·编程 ⁄ 共 2327字 ⁄ 字号 暂无评论

    求数组中第K大的数可以基于快排序思想,步骤如下:
      1、随机选择一个支点

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

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

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

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

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

     以上思想的代码实现如下

/**
线性时间复杂度求数组中第K大数
** author :liuzhiwei 
** data   :2011-08-07  
**/ 
#include "iostream" 
using namespace std; 
 
//基于快速排序思想,求数组a中第k大的数,low和high分别为数组的起始和结束位置 
//时间复杂度为o(n),n为数组的长度 
//1<=k<=n 
//如果存在,返回第k大数的下标,否则返回-1 
 
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++;              //比支点大的数的个数为count-1 
        } 
    } 
    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(void) 

    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; 

         稍微改动一下,就可以修改为求数组中第K小数
         完整的代码如下

/**
线性时间复杂度求数组中第K小数
** author :liuzhiwei 
** data   :2011-08-07  
**/ 
#include "iostream" 
using namespace std; 
 
//基于快速排序思想,求数组a中第k小的数,low和high分别为数组的起始和结束位置 
//时间复杂度为o(n),n为数组的长度 
//1<=k<=n 
//如果存在,返回第k小数的下标,否则返回-1 
 
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++;              //比支点小的数的个数为count-1 
        } 
    } 
    swap(a[m], a[low]);           //将支点放在左、右两部分的分界处 
    if(k < count) 
    { 
        return selectk(a, low, m - 1, k); 
    } 
    else if( k > count) 
    { 
        return selectk(a, m + 1, high, k - count); 
    } 
    else 
    { 
        return m; 
    } 

int main(void) 

    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, 23); 
    cout<<(r == -1 ? r : a[r])<<endl; 
    system("pause"); 
    return 0; 

给我留言

留言无头像?