C++实现查找中位数的O(N)算法和Kmin算法

中位数

• 中位数指的是一组数据中间位置的数。
• 对于一组无序数据而言，可以使用快速排序、堆排序等算法求出其中位数。
• 但是这些算法的时间复杂度较高。
• 在此讨论的是时间复杂度为O(N)的算法。

O(N)算法

• O(N)算法的基本思想：将一组数据分成若干组，然后对于每一组进行处理。
• 首先随机选择一个数作为参考数，然后将数据分为两组，一组比参考数小，另一组比参考数大。
• 此时有三种情况：
• 分组后小于参考数的组中元素个数等于N/2，则中位数为参考数；
• 小于参考数的组中元素个数小于N/2，在大于参考数的组中递归搜索中位数；

• 小于参考数的组中元素个数大于N/2，在小于参考数的组中递归搜索中位数。

• 通过以上三种情况，可以保证每次递归后搜索的数据量都会减半，实现了O(N)的时间复杂度。

#include<bits/stdc++.h>
using namespace std;

int nums[100005];

// 搜索中位数
int searchmid(int l,int r,int k){
    if(l+1>=r)return nums[l];
    int i=l+1,j=r-1,x=nums[l];
    while(i<j){
        while(nums[i]<=x && i<j)i++;
        while(nums[j]>x)j--;
        if(i<j)swap(nums[i],nums[j]);
    }
    if(nums[l]<nums[j-1])swap(nums[l],nums[j-1]);
    else{
        j--;
        swap(nums[l],nums[j]);
    }
    if(j-l==k)return nums[j];
    if(j-l>k)return searchmid(l,j,k);
    else return searchmid(j,r,k-j+l);
}

int main(){
    // 读入数据
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>nums[i];
    // 搜索中位数
    int ans=searchmid(0,n,k);
    // 输出结果
    cout<<ans<<endl;
    return 0;
}

Kmin算法

• Kmin算法的目标是查找一组数据中第K小的数据。
• 思路为沿用O(N)算法的分组思路，对于每一组确定其最小值$min_l$和最大值$max_r$，找到一组数，使其小于或等于$max_r$，大于或等于$min_l$，则其中必然包含第K小的数。

#include<bits/stdc++.h>
using namespace std;

int nums[100005];

// 寻找第k小的数
int searchkmin(int l,int r,int k){
    if(l+1>=r)return nums[l];
    int m=rand()%(r-l)+l;
    swap(nums[m],nums[l]);
    int i=l+1,j=r-1,x=nums[l];
    while(i<j){
        while(nums[i]<=x && i<j)i++;
        while(nums[j]>x)j--;
        if(i<j)swap(nums[i],nums[j]);
    }
    if(nums[l]<nums[j-1])swap(nums[l],nums[j-1]);
    else{
        j--;
        swap(nums[l],nums[j]);
    }
    if(j-l==k)return nums[j];
    if(j-l>k)return searchkmin(l,j,k);
    else return searchkmin(j,r,k-j+l);
}

int main(){
    // 读入数据
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>nums[i];
    // 寻找第k小的数
    int ans=searchkmin(0,n,k);
    // 输出结果
    cout<<ans<<endl;
    return 0;
}

示例

示例一

输入：

5 3
3 4 2 5 1

输出：

3

说明：

查找第三小的数。

分组后：小于2的数组合为{1}，大于2的数组合为{3,4,5}。

小于2的数组合包含0个第三小的数，需要在大于2的数组合中查找第三小的数。

分组后：小于4的数组合包含3个数，大于4的数组合包含1个数。

小于4的数组合中第三小的数位于大于4的数组合中，继续查找第三小的数。

分组后：小于3的数组合中包含两个数，等于3的数组合中包含一个数。

查找结束，找到的第三小的数为3。

示例二

输入：

7 5
-1 2 -2 5 10 -5 4

输出：

2

说明：

查找第五小的数。

分组后：小于$-2$的数组合为$-5$，等于$-2$的数组合为空，大于$-2$的数组合为$-1,2,5,10,4$。

小于$-2$的数组合包含0个第五小的数，需要在大于$-2$的数组合中查找第五小的数。

分组后：小于$4$的数组合包含4个数，大于$4$的数组合包含2个数。

小于$4$的数组合中包含第五小的数，继续查找第五小的数。

分组后：小于$2$的数组合为$-1,-2$，等于$2$的数组合为空，大于$2$的数组合为$5,10$。

小于$2$的数组合包含3个第五小的数，需要在大于$2$的数组合中查找第$5-3=2$小的数。

分组后：小于$5$的数组合包含2个数，等于$5$的数组合包含一个数。

查找结束，找到的第五小的数为2。