区块链技术博客
www.b2bchain.cn

[排序] 第k个数(模板+快速选择算法)

这篇文章主要介绍了[排序] 第k个数(模板+快速选择算法)的讲解,通过具体代码实例进行20193 讲解,并且分析了[排序] 第k个数(模板+快速选择算法)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=20193

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

    • 0. 前言
    • 1. 快速选择算法

0. 前言

快速选择算法的思想还是很厉害的。是快速排序的应用,一般将一次快排称为做了一次 partition 操作。c++ stl 也将该函数纳入其中,感兴趣可取查看相关 API

1. 快速选择算法

786. 第k个数

[排序] 第k个数(模板+快速选择算法)

本质: 快排应用

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( l o g n ) O(logn) O(logn),基于递归,用到栈空间

思路:

  • 一次快排,数轴左边都 <=x,数轴右边都 >= x
  • 左边的元素个数为 s = j - l + 1
  • 如果 k <= s ,说明第 k 个数还在左半区间,则下次就递归左半区间
  • 否则,递归右半区间的时候,寻找右半区间的第 k-s 个数即可

注意: 这里是 s = j - l + 1,而不是 s = i - l因为 while 循环结束,i,j 可能相等,可能穿越。区间就被分成 [l,j] 为左半边区间,[i,r] 为右半边区间。其中 [l, j] 是小于等于基准值的数,右半边是大于等于基准值的数。

模板代码:

#include <iostream> #include <algorithm>  using namespace std;  const int N = 1e5+5;  int n; int q[N];  void quick_sort(int l, int r) {     if (l >= r) return ;     int x = q[l+r>>1], i = l - 1, j = r + 1;     while (i < j) {         do i++; while (q[i] < x);         do j--; while (q[j] > x);         if (i < j) swap(q[i], q[j]);     }     quick_sort(l, j);	// j对应 q[l]     quick_sort(j + 1, r); }  int main() {     cin >> n;     for (int i = 0; i < n; ++i) cin >> q[i];          quick_sort(0, n - 1);          for (int i = 0; i < n; ++i) cout << q[i] << ' ';          return 0; } 

本文转自互联网,侵权联系删除[排序] 第k个数(模板+快速选择算法)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » [排序] 第k个数(模板+快速选择算法)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们