frank

浅谈算法-查找第k小
2018-08-08 16:00 update:更新sort的测试结果更新nth_element的测试结果2018...
扫描右侧二维码阅读全文
08
2018/08

浅谈算法-查找第k小

2018-08-08 16:00 update:

  1. 更新sort的测试结果
  2. 更新nth_element的测试结果

2018-08-08 20:00 update:

  1. 声明部分程序出处
  2. 添加关于algorithm中的nth_element函数
  3. 添加参考文献

1 前言

在生活中,我们常常会查找第k小,在计算机中也有广泛应用,这篇文章,我们就来探究一下查找第k小的算法。

2 思路

2.1 朴素排序算法

说到第k小,想必大家第一想到的算法就是排序,直接来一遍选择、冒泡,输出a[k]不就行了吗?请注意,这个数字序列中,可能会存在相同的元素。此时,我们要向一种方法进行排重

排重方法有以下几种选择:

  • flag数组,flag[x]表示x是否出现过,出现过为1,没出现过为0
  • STL模板库中的集合set存储元素,没出现过压进数组、set,出现过直接丢掉
  • 正常排序,输出时判重

第一种方法有一个明显的缺陷:数不能过大。

当数大到108时,空间已经大到100MB左右,显然当数较大时此方法是不可取的,当数较小的时候,这种方法速度最快,可以按照O(1)左右计算,总时间复杂度最多为O(n^2)(当有很多重复元素时,速度会更快)。

代码如下:

#include<iostream>
#include<cstdio>
using namespace std;

long long a[500000],n,cnt,x,k,flag[500000];

int main()
{
    cin>>n>>k;
    for (long long i=1;i<=n;i++)
    {
        cin>>x;
        if (!flag[x]) a[++cnt]=x,flag[x]=1;
    }
    for (long long i=1;i<cnt;i++)
        for (long long j=i+1;j<=cnt;j++)
            if (a[i]>a[j]) swap(a[i],a[j]); //选择排序
    cout<<a[k]<<'\n';
    return 0;
}

第二种方法使用了set,而set的内部结构使用了红黑树,插入和查询的时间复杂度都是O(logn),所以判重时的时间复杂度为O(nlogn),加上选择排序,总时间复杂度为O(n^2)(当有很多重复元素时,速度会更快)。

代码如下:

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;

long long a[1000000],n,cnt,x,k;
set<long long> flag;

void flag_insert(long long v)
{
    if (flag.count(v)) return;
    flag.insert(v);
    a[++cnt]=v;
}

int main()
{
    cin>>n>>k;
    for (long long i=1;i<=n;i++)
    {
        cin>>x;
        flag_insert(x); //判重
    }
    for (long long i=1;i<cnt;i++)
        for (long long j=i+1;j<=cnt;j++)
            if (a[i]>a[j]) swap(a[i],a[j]); //选择排序
    cout<<a[k]<<'\n';
    return 0;
}

第三种方法实现起来略复杂与前两种,在输出的时候for循环判重,时间复杂度最多为O(n),总时间复杂度为O(n^2)(因为输入时没有判重,所以排序时速度略慢)。

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;

int a[100000],n,cnt=0x3f3f3f3f,x,k,t;

int main()
{
    scanf("%d%d",&n,&k); //cin>>n>>k;
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]); //cin>>a[i];
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
            if (a[i]>a[j]) swap(a[i],a[j]); //选择排序
    for (int i=1;i<=n;i++)
    {
        if (cnt!=a[i]) {cnt=a[i];t++;} //判重
        if (t==k) {printf("%d",a[i]);return 0;}
    }
    return 0;
}

以上,是选择排序+判重的方法,时间复杂度均为O(n^2)。

2.2 快速排序算法

利用快速排序优化以上算法,时间复杂度可达O(nlogn)。但是,当所有元素相等时,普通的快排算法便会退化至O(n^2),当然,你也可以用三向切分快排来优化这个问题,本文不做介绍。使用快排使时间复杂度达到O(nlogn)对上述第二种方法已经足够了,但是相对第一种方法(O(1)),总时间复杂度仍被快排大大拖慢,所以算法仍有优化的余地。

快速排序的本质是分治,一般分为以下两种思路:

  • 取中间数作为基准数,不断交换左右区间的数,使左边的数小于基准数,右边的数大于基准数
  • 取区间末尾数为基准数,不断校正,最后将末位数换到合适的位置,使左边的数小于基准数,右边的数大于基准数

你有没有发现什么???

在交换的同时,因为左边的数小于基准数,右边的数大于基准数,所以基准数所处在a[k]的位置,即为第k小。

我们来举个栗子

举个栗子

有这样一个序列

{ 1 , 8 , 7 , 4 , 9 , 3 , 5 , 2 , 6 }

我们取6为基准数

int partition(int A[],int p, int r) {
    int x = A[r];
    int i = p - 1;
    
    int j;
    for (j = p; j <= r - 1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return (i+1);
}

p为起始位置,r为结束位置

i在不断交换过程中,永远指向小于A[r](基准数)的最后一个。

最后排列成如下序列

{ 1 , 4 , 3 , 5 , 2 , 7 , 8 , 9 , 6 }

最后再将A[i+1]和A[r]交换一下

排成下面这个序列

{ 1 , 4 , 3 , 5 , 2 , 6 , 8 , 9 , 7 }

i+1即表示了A[r]是第i+1小,即第6小

相信以上所讲内容都可以理解,这道题的解法也显而易见,在快排的同时,判断i+1是不是等于k,等于k直接返回值,如果小于k,则在右区间找,大于k而在左区间找。

但是上述方法仍然有一个大bug,如果出题人除了一组很坑的数据,每次最后一个数(基准数)都恰恰不为k,又该怎么办?

上述所说的bug很好找出一个例子,有1000000个数,求第2小。在此处我们设定这1000000个数不同,且已是从小到大排好的,忽略排重过程。那么基准数依次为1000000、500000、250000、125000 ······ 2,这使得算法会退化到O(nlogn),请大家想一想,如何有效的避免这种状况?

答案是三个字!!!

随机数

我们可以,在序列中随机找一个数,如A[i],与A[r]交换一下,就做到了任意的基准数,避免以上bug。

int randomized_partition(int A[], int p, int r) {
    int i;
    i = (rand() % (r - p + 1)) + p;
    swap(A[r],A[i]);
    return partition(A,p,r);
}

注意:不要忘了随机化种子

当然,你的运气也可能差到极点,每次都取末尾,那么,你懂的😏😏😏

综合上述所有内容,我们可以写出如下一段找第k小的程序:

#include <cstdlib>
#include <cstdio> 
#include <iostream>
#include <ctime>

using namespace std;
const int MAXN = 100005;

int partition(int A[],int p, int r) {
    int x = A[r];
    int i = p - 1;
    
    int j;
    for (j = p; j <= r - 1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return (i+1);
}
int randomized_partition(int A[], int p, int r) {
    int i;
    i = (rand() % (r - p + 1)) + p;
    swap(A[r],A[i]);
    return partition(A,p,r);
}

int randomized_select(int A[], int p, int r, int i) {
    if (p == r) 
        return A[p];
    int q;
    
    q = randomized_partition(A,p,r);
    int k = q - p + 1;
    if (i == k)
        return A[q];
    else if(i < k) 
            return randomized_select(A,p,q-1,i);
    else 
        return randomized_select(A,q+1,r,i-k);
}
int main() {
    int n,k;
    int A[MAXN];
    cin >> n >>k;
    srand((unsigned)time(NULL));
    for (int i =1; i <= n; i++) cin >> A[i];
    cout <<randomized_select(A,1,n,k) <<endl;
    return 0;
}

我们再使用第一种方法进行排重,最终代码如下:

#include <cstdlib>
#include <cstdio> 
#include <iostream>
#include <ctime>

using namespace std;
const int MAXN = 100005;

int partition(int A[],int p, int r) {
    int x = A[r];
    int i = p - 1;
    
    int j;
    for (j = p; j <= r - 1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return (i+1);
}
int randomized_partition(int A[], int p, int r) {
    int i;
    i = (rand() % (r - p + 1)) + p;
    swap(A[r],A[i]);
    return partition(A,p,r);
}

int randomized_select(int A[], int p, int r, int i) {
    if (p == r) 
        return A[p];
    int q;
    
    q = randomized_partition(A,p,r);
    int k = q - p + 1;
    if (i == k)
        return A[q];
    else if(i < k) 
            return randomized_select(A,p,q-1,i);
    else 
        return randomized_select(A,q+1,r,i-k);
}
int main() {
    int n,k,cnt=0,x;
    int A[MAXN],flag[MAXN]={0};
    cin >> n >>k;
    srand((unsigned)time(NULL));
    for (int i =1; i <= n; i++)
    {
        cin >> x;
        if (!flag[x]) A[++cnt] = x,flag[x] = 1;
    }
    n = cnt;
    cout <<randomized_select(A,1,n,k) <<endl;
    return 0;
}

注:上述2个程序,均改自算法导论的第9章第2节

2.3 STL中的nth_element函数

STL中的algorithm提供了nth_element函数,通过调用nth_element(A+1, A+k+1, A+n+1) 方法可以使第k大元素处于第k位置(从1开始,其位置是下标为k的元素),并且比这个元素小的元素都排在这个元素之前,比这个元素大的元素都排在这个元素之后,但不能保证整个序列是是有序的

那么为什么要选择这个函数呢,这就和复杂度有关了,nth_element的空间复杂度为O(1),在数据量大的时候时间复杂度为O(n),数据少的情况最坏为O(n^2),因为函数原理是随机访问,但实际运用过程中,基本都会是O(n)的时间复杂度。所以说是非常迅速的。

因此,这个函数也是可以采用的,效果详见2.4节中的表格。

程序如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

long long a[500000],n,cnt,x,k,flag[500000];

int main()
{
    cin>>n>>k;
    for (long long i=1;i<=n;i++)
    {
        cin>>x;
        if (!flag[x]) a[++cnt]=x,flag[x]=1;
    }
    nth_element(a+1, a+k+1, a+cnt+1);
    cout<<a[k]<<endl; 
}

2.4 总结

在这一章中,我们分别用朴素的排序方法和快排的分治思想解决了两道题。

为了测试它们的效率和内存,我生成了100000的数据(数最大100000)进行测试,得到以下结果:

算法时间空间
选择排序(一)14556ms3351KB
选择排序(二)14640ms5304KB
选择排序(三)RERE
sort+排重(一)44ms3347KB
STL中的nth_element+排重(一)40ms3277KB
快排的分治思想24ms2632KB

表格中选择排序(三)RE是因为它需要过大的数组超过了全局变量所能开的最大范围。快排的分治思想实现的程序时空方面都大大提高。

大家也可以试试看:传送门(采用CYaRon生成测试数据)

(以上由洛谷帮助评测)

3 完结撒花 ★,°:.☆( ̄▽ ̄)/$:.°★

感谢大家的支持,如有更好的算法,欢迎指出!

参考文献:

特别鸣谢:

Last modification:September 11th, 2018 at 10:16 pm
If you think my article is useful to you, please feel free to appreciate

2 comments

  1. 悠悠

    小哥哥,你好厉害

  2. 沈叔叔

    不错,虽然看不懂

Leave a Comment