无序数组求第k大/第k小的数

时间：2022-12-30 15:26:53

根据http://www.cnblogs.com/zhjp11/archive/2010/02/26/1674227.html

博客中所总结的7种解法，我挑了其中的解法3和解法6进行了实现。

解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
           1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
           2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

 

#include<stdio.h>
#include<string.h>
int par(int a[],int l,int r){
int x=a[l];
while(l<r){
while(l<r&&a[r]<=x)    --r;
        a[l]=a[r];
while(l<r&&a[l]>=x)    ++l;
        a[r]=a[l];
    }
    a[l]=x;
return l;
}
int search(int a[],int l,int r,int k){
if(l<=r){
int p = par(a,l,r);
if(p-l+1==k)    return p;
else if(p-l+1<k){
return search(a,p+1,r,k-(p-l+1));
        }else{
return search(a,l,p-1,k);
        }
    }
}
int main(){
int n,k;
int a[100];
    scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    printf("%d\n",a[search(a,1,n,k)]);
return 0;
}

 

 解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)

注意：这里要求第k大的数，所以要构建的是小顶堆，并且只有当新进来的数大于堆顶也就是目前k个数里最小的数时，才有可能是第k个大的数，才将其加入堆。

 

#include<stdio.h>
#include<string.h> 
#include<iostream>
using namespace std;
void heapAdd(int a[],int i,int num){
    a[i]=num;
for(int j=i>>1;j&&i&&a[i]<a[j];i=j,j>>=1)
        swap(a[i],a[j]);
}
void heapDown(int a[],int i,int n){
for(int j=i<<1;j<=n;i=j,j<<=1){
if(j+1<=n&&a[j+1]<a[j])    j++;
if(a[i]>a[j])    swap(a[i],a[j]);
    }
}
int a[100],n,k,b[100];
int main(){
    scanf("%d%d",&n,&k);
int cnt=0;
for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
if(cnt<k){
            heapAdd(b,++cnt,a[i]);
        }else{
if(b[1]<a[i]){
                b[1]=a[i];
                heapDown(b,1,k);
            }
        }
    }
    printf("%d\n",b[1]);
return 0;
}

 如果要求的是第k小的数，则把相应的判断条件改一下就可以了

标签：

相关文章