2021-7-23 快速选择算法求第k个数

2021/7/23 9:35:45

本文主要是介绍2021-7-23 快速选择算法求第k个数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第一章基础算法课

前言

学习思路:课上理解算法思想,课下记忆代码并上手题目,每道题目代码写上3到5遍,重复记忆。

Acwing在线题库

1、快速排序

算法思想:分治策略

时间复杂度:0(nlogn)

算法步骤:

  • 选择分界点x,三种选法,左边点q[l],中间点q[(l+r)/2],右边点q[r]
  • 划分为两个区间,左边区间left所有数<=x,右边区间right所有数>=x
  • 递归排序左区间left和右区间right

上代码:

void quick_sort(int q[],int l,int r){
    if(l>=r) return;
    int x=q[l];
    int i=l-1,j=r+1;
    while(i<j){
        while(q[++i]<x);  //相当于do i++; while(q[i]<x);
        while(q[--j]>x);  //相当于do j--; while(q[j]>x);
        if(i<j) swap(i,j);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

2. 快速选择——求第k个数

题目:给定一个长度为 n 的整数数列,以及一个整数 k,请用快速选择算法求出数列从小到大排序后的第 k个数。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 n 个整数(所有整数均在 1∼1091∼109 范围内),表示整数数列。

输出格式

输出一个整数,表示数列的第 k 小数。

对于求第k个数的问题,我们很容易想到使用排序法解决,但是排序算法的时间复杂度最小也是0(nlogn),那么怎样才能更加优雅高效的解决第k小数的问题呢,这就不得不要说一说快速选择算法了。

快速选择算法是基于快速排序算法的变形,它的总体思路和快速排序是一样的,选择一个元素作为基准元素,将小于基准的元素和大于基准的元素分别放在左右两边,不同的是,快速选择算法每次不用递归访问左右两边,而是递归进入其中一边继续进行查找,这就将平均时间复杂度从O(nlogn)降到了O(n)。

算法步骤:

  • 同样是选择分界点x,三种选法q[l],q[(l+r)/2],q[r]
  • 划分为两个区间left和right,left中所有元素都小于x,right中所有元素都大于x,记录left和right的区间长度分别为Sl和Sr
  • 若k小于等于Sl,则递归访问左区间left;若k大于Sl,则递归访问右区间Sr,此时k为右区间right中第k-Sl小的数

快速选择代码:

quick_select(q[],int l,int r,int k){  //寻找第k小的数
    int x = q[l];
    int i = l-1,j = r+1;
    
    if(l == r) return q[l];
    while(i < j){
        while(q[++ i] < x);
        while(q[-- j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    int sl = j - l + 1;
    if(k <= s1) return quick_select(q,l,j,k);
    else return quick_select(q,j+1,r,k-s1);
}

啊啊啊,调试了好久才通过,代码太生疏了

在这里插入图片描述



这篇关于2021-7-23 快速选择算法求第k个数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程