当前位置：首页 > news >正文

【分治法】第k个数（快速选择算法，结合快速排序）

news 来源：原创 2024/5/3 23:24:06

🌵🌵🌵前言

✨你好啊，我是“ 怪& ”，是一名在校大学生哦。
🌍主页链接：怪&的个人博客主页
☀️博文主更方向为：课程学习知识、作业题解、期末备考、项目实战等，随着专业的深入会越来越广哦…一起期待。
❤️一个“不想让我曾没有做好的也成为你的遗憾”的博主。
💪很高兴与你相遇，一起加油！

题目：

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 k 小数。
数据范围
1≤n≤100000,
1≤k≤n
输入样例:
5 3
2 4 1 5 3
输出样例：
3

解法1、用j分段

a[j]<=x,a[j]算入左半段,分段为(l,j)与(j+1,r)
避免右边界问题 x=a[(l+r)/2]或x=a[l]

int length=j-l+1; //j算入左半段
if(length>=k) return quick_sort(l,j,k);
else return quick_sort(j+1,r,k-length);

#include <iostream>

using namespace std;
const int N =1e5+10;
int a[N];
int n,k;//数字个数，与第k个数


int quick_sort(int l,int r,int k){
    if(l==r) return a[l]; //区间内仅一个数，直接返回
    int x=a[l+r>>1]; 
    //int x=a[(l+r)/2];  //避免右边界问题 x=a[(l+r)/2]或x=a[l]
    int i=l-1,j=r+1; //循环每次先移动一位才判断
    
    while(i<j){//两者未穿过则一直执行
        do{
            i++;    //移动至a[i]>=x
        }while(a[i]<x);
        do{
            j--;    //移动至a[j]<=x
        }while(a[j]>x);        
        if(i<j) swap(a[i],a[j]); //两者未穿过才交换
    }
    //i>=j
    //此时a[i]>=x,a[i]左方皆<=x,a[i]右方(含a[i])皆>=x
    //此时a[j]<=x,a[j]左方(含a[j])皆<=x,a[j]右方皆>=x
    
    int length=j-l+1;
    if(length>=k) return quick_sort(l,j,k);
    else return quick_sort(j+1,r,k-length);
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int out=quick_sort(0,n-1,k);
    cout<<out<<endl;
    return 0;
}

解法2、用i分段

a[i]>=x,a[i]算入右半段,分段为(l,i-1)与(i,r)
避免左边界问题 x=a[(l+r+1)/2]或x=a[r]

int length=i-l;
if(length>=k) return quick_sort(l,i-1,k);
else return quick_sort(i,r,k-length);

#include <iostream>

using namespace std;
const int N =1e5+10;
int a[N];
int n,k;//数字个数，与第k个数


int quick_sort(int l,int r,int k){
    if(l==r) return a[l]; //区间内仅一个数，直接返回
    int x=a[(l+r+1)/2];  //避免左边界问题 x=a[(l+r+1)/2]或x=a[r]
    // int x=a[r]; // √可用    
    int i=l-1,j=r+1; //循环每次先移动一位才判断
    
    while(i<j){//两者未穿过则一直执行
        do{
            i++;    //移动至a[i]>=x
        }while(a[i]<x);
        do{
            j--;    //移动至a[j]<=x
        }while(a[j]>x);        
        if(i<j) swap(a[i],a[j]); //两者未穿过才交换
    }
    //i>=j
    //此时a[i]>=x,a[i]左方皆<=x,a[i]右方(含a[i])皆>=x
    //此时a[j]<=x,a[j]左方(含a[j])皆<=x,a[j]右方皆>=x
    
    int length=i-l;
    if(length>=k) return quick_sort(l,i-1,k);
    else return quick_sort(i,r,k-length);
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int out=quick_sort(0,n-1,k);
    cout<<out<<endl;
    return 0;
}