Java教程

算法学习2:快速选择

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

快速选择

  • 1 基本思想
  • 2 代码

本文是在听过AcWing算法基础课程之后留下自用的笔记,如有侵权会删除。感觉AcWing的课还是蛮好的,课程地址如下:

https://www.acwing.com/activity/content/introduction/11/

知识点对应的题目为:https://www.acwing.com/problem/content/788/

1 基本思想

快速选择算是快速排序的一种排序吧,感觉差不多,快速排序的方法为:

  1. 找到分界点x:q[L], q[(L+R)/2], q[R]
  2. 调整元素顺序,使左边所有数Left <= x,右边所有数 Right>=x
  3. 递归排序Left,递归排序 Right

详见:https://blog.csdn.net/shaojie_45/article/details/116223091

快速选择就是在快排的基础上记录左右两边元素的个数:

具体来说,设左半部分的个数为 S L S_L SL​,右半部分个数为 S R S_R SR​, S L S_L SL​中的数一定是小于 S R S_R SR​中的数的。因此,如果 k ≤ S L k\leq S_L k≤SL​,则递归寻找左边的第k个数;如果 k ≥ S L k\geq S_L k≥SL​,则递归寻找右边的第 k − S L k-S_L k−SL​个数。

设数组有n个元素,第一次遍历要访问n个元素,第二遍访问n/2个,第三遍访问n/4个,以此类推。总的时间复杂度为 O ( n ) O(n) O(n)

2 代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n,k;
int q[N];

int quickRank (int l, int r, int k){
    if (l == r)  
        return q[l];
    int val = q[l];
    int tempL = l - 1;
    int tempR = r + 1;
    while (tempL < tempR){
        do tempL++; while(q[tempL] < val);
        do tempR--; while(q[tempR] > val);
        if (tempL < tempR)
            swap(q[tempL],q[tempR]);
    }
    if (tempR + 1 - l >= k)
        return quickRank(l,tempR,k);
    else
        return quickRank(tempR + 1,r,k - tempR - 1 + l);
        

}

int main(){
    scanf("%d %d",&n,&k);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    printf("%d", quickRank(0,n-1,k));
    return 0;
    
}

一个小提示:递归、计数等最好用一个指针来计算、划分,比如都是用tempR或者都用tempL,不然容易出错

这篇关于算法学习2:快速选择的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!