A13 第k小的数 • EH's Blog

题目情境#

https://www.luogu.com.cn/problem/P1923 ↗

题目描述

输入 $n$ 个数字 $a_i$ ，输出这些数字中第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

第一行有两个整数，分别表示 $n$ 和 $k$ 。

第二行有 $n$ 个整数，第 $i$ 个数表示 $a_i$ 。

输出格式

一个整数，表示第 $k$ 小的数。

输入输出样例

输入 #1

5 1
4 3 2 1 5

plaintext

输出 #1

plaintext

说明/提示

对于 $100\%$ 的数据， $1\le a_i<{10}^9$ ， $1 \le n < 5\times 10^6$ ，且 $n$ 为奇数。

算法解析#

QuickSelect（快速选择）算法，用来在无序数组中快速找到第 k 小的元素。它先选一个基准值 x，像快速排序一样把数组划分成“左边 ≤ x、右边 ≥ x”两部分，但不会递归处理两边，而是只进入包含第 k 小元素的那一边继续查找，因此平均时间复杂度是 O(n)，比完整排序的 O(n log n) 更快。

C++里可以直接使用nth_element(begin, nth, end)

Python代码实现#


import sys
sys.setrecursionlimit(5000000)
def qnth_element(l, r):
    global a
    if l == r:
        return a[l]
    i = l - 1
    j = r + 1
    x = a[(l + r) // 2]
    while i < j:
        while 1:
            i += 1
            if not a[i] < x:
                break
        while 1:
            j -= 1
            if not a[j] > x:
                break
        if i < j:
            a[i], a[j] = a[j], a[i]
    if k <= j:
        return qnth_element(l, j)
    else:
        return qnth_element(j + 1, r)
n, k = map(int, input().split())
a = list(map(int, input().split()))
print(qnth_element(0, n - 1))

python

C++代码实现#

#include <iostream>
using namespace std;

int n,k,a[5000010];

int qnth_element(int l, int r){
  if(l==r) return a[l];
  int i=l-1, j=r+1, x=a[(l+r)/2];
  while(i<j){
    do i++; while(a[i]<x); //向右找>=x的数
    do j--; while(a[j]>x); //向左找<=x的数
    if(i<j) swap(a[i],a[j]);
  }
  if(k<=j) return qnth_element(l,j);
  else return qnth_element(j+1,r);
}

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