算法学习2:快速选择
2021/4/29 14:25:17
本文主要是介绍算法学习2:快速选择,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速选择
- 1 基本思想
- 2 代码
本文是在听过AcWing算法基础课程之后留下自用的笔记,如有侵权会删除。感觉AcWing的课还是蛮好的,课程地址如下:
https://www.acwing.com/activity/content/introduction/11/
知识点对应的题目为:https://www.acwing.com/problem/content/788/
1 基本思想
快速选择算是快速排序的一种排序吧,感觉差不多,快速排序的方法为:
- 找到分界点x:q[L], q[(L+R)/2], q[R]
- 调整元素顺序,使左边所有数Left <= x,右边所有数 Right>=x
- 递归排序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:快速选择的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)