从n个无序数中找出第K大的数

时间:2022-06-01 21:20:46

 

  •  遇到题目为从n个无序数组中找出第K大的数,最开始想到的就是冒泡排序、选择排序等,每次找到一个最大(或最小)的,但是很明显需要时间复杂度为O(n*k)!具体代码细节参考findK_2
  • 改进一点的算法有根据快速排序的思想,时间复杂度达到O(n)。想象一下,第k大,说明前面有k-1个元素是比第k个元素大,那么利用快速排序的思想,将大于轴值(暂且固定第一个元素)的放在左边,小于轴值的放在右边。那么一趟划分下来,如果左边的元素数目大于k,那么则说明下一趟继续在左边进行划分;相反,则一趟继续在右边进行划分...直到划分轴索引等于k。具体代码细节参考findK_1(想一想,划分轴索引为k的时候,根据快速排序划分的思想,是不是前面有k-1个比它大的数,那么是不是找到了第k大的数?)
  • 当内存中不能一次性存下很多数的时候,O(n)的算法就不能满足需求了,这时候有O(nlogk)的算法,即根据堆排序的思想,建立一个k的元素的大根堆,遍历整个数组,不断调整并输出。具体代码细节参考findK_3
/***************** n个无序数中求第K大数 *****************/ 
#include<iostream>
#include<cstdio> 
#include<algorithm> 
using namespace std;

/*冒泡排序思想,时间复杂度:O(n*k)*/
int findK_2(int a[], int k){
    bool flag = true;
    for(int i=0;i<k && flag;i++){
        flag=false;
        for(int j=8;j>i;j--){
            if(a[j]>a[j-1]){
                swap(a[j],a[j-1]);
                flag=true;
            }
        }
    }
    return a[k-1];
}

/*堆排序思想,时间复杂度:O(nlogk) */
//将a[s...m]调正为堆,其中除s位置值都符合堆定义 
void AdjustHeap(int a[], int s, int m){
    int j, tmp=a[s];
    for(j=s*2;j<=m;j*=2){
        if(j<m && a[j]<a[j+1]){
            ++j;
        }
        if(a[j]<=tmp){
            break;
        }
        a[s]=a[j];
        s=j;
    }
    a[s]=tmp;
}

int findK_3(int a[], int k){
    int len = 9;
    //建堆 
    for(int i=(len-1)/2;i>=0;i--){
        AdjustHeap(a, i, len-1);
    }
     
    //堆排序
    for(int i=len-1;i>=len-k;i--){
        swap(a[i], a[0]);
        AdjustHeap(a, 0, i-1);
    }
    
    return a[len-k]; 
}


/*快速排序思想,时间复杂度:O(n) */
int Partition(int low, int high, int a[]){
    int p = a[low]; //哨兵 
    while(low<high){
        while(low<high && a[high]<=p){
            high--;
        }
        a[low]=a[high];
        while(low<high && a[low]>p){
            low++;
        } 
        a[high] = a[low];
    }
    a[low] = p;
    return low;
} 

int findK_1(int a[], int k, int low, int high){
    int tmp = Partition(low, high, a);
    if(tmp==k-1){
        return a[tmp];
    }else if(tmp>k-1){
        findK_1(a, k, low, tmp-1);
    }else{
        findK_1(a, k, tmp+1, high);
    }
}

int QuickSort(int a[], int low, int high){
    if(low<high){
        int tmp = Partition(low, high, a);
        QuickSort(a, low, tmp-1);
        QuickSort(a, tmp+1, high);
    }
}


int main(){
    int a[] = {15,3,2,6,1,10,13,11,8};
    int b[] = {15,3,2,6,1,10,13,11,8};
    int c[] = {15,3,2,6,1,10,13,11,8};
    int d[] = {15,3,2,6,1,10,13,11,8};
    int k;
    cout<<"输入k: ";
    cin>>k;
    QuickSort(a, 0, 8);
    cout<<"快速排序后:"<<endl;
    
    for(int i=0;i<=8;i++){
        printf("%d%c",a[i],i!=8?' ':'\n');
    } 
    
    int big_k_1 = findK_1(b, k, 0, 8);
    printf("利用快速排序思想O(n),第%d大的数为:%d\n", k, big_k_1);

    int big_k_2 = findK_2(c, k);
    printf("利用冒泡排序思想O(n*k),第%d大的数为:%d\n", k, big_k_2);

    int big_k_3 = findK_3(d, k);
    printf("利用堆排序思想O(nlogk),第%d大的数为:%d\n", k, big_k_3);
    return 0;
}

 


代码运行如下:

输入k: 3 快速排序后: 15 13 11 10 8 6 3 2 1 利用快速排序思想O(n),第3大的数为:11 利用冒泡排序思想O(n*k),第3大的数为:11 利用堆排序思想O(nlogk),第3大的数为:11