鱼C论坛

 找回密码
 立即注册
查看: 464|回复: 1

[已解决]快速选择算法

[复制链接]
发表于 2024-1-15 17:11:54 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
typedef pair<int,int>pii;
const int N=2e5+10;
// 用快速选择算法
int n,k;
int q[N];
int quick_sort(int l,int r,int k)
{
    if(l==r)return q[l];
    int x=q[l],i=l-1,j=i+1;
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);

    }
    int sl=j-l+1;// 左边区间有多少个数
    if(k<=sl)return quick_sort(l,j,k);
    return quick_sort(j+1,r,k-sl);


}

void solve()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    cout<<quick_sort(0,n-1,k)<<endl;
    

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t=1;
    while(t--)
    {
        solve();
    }

}
为什么会没有输出呢
最佳答案
2024-1-15 17:12:42
快速选择算法是一种用于在无序数组中寻找第k个最小元素的算法。它的思想类似于快速排序,通过将数组分成两部分,其中一部分比pivot元素小,另一部分比pivot元素大。然后根据pivot元素所在的位置,判断第k个最小元素在哪一部分,并对相应的部分进行递归处理。

以下是一个使用快速选择算法寻找第k个最小元素的示例代码:
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最右边的元素作为pivot
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

int quickSelect(int arr[], int low, int high, int k) {
    if (low == high) {
        return arr[low];
    }
    
    int pivotIndex = partition(arr, low, high);
    int rank = pivotIndex - low + 1;
    
    if (rank == k) {
        return arr[pivotIndex];
    } else if (rank < k) {
        return quickSelect(arr, pivotIndex + 1, high, k - rank);
    } else {
        return quickSelect(arr, low, pivotIndex - 1, k);
    }
}

int main() {
    int arr[] = {3, 1, 5, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;  // 寻找第2个最小元素
    
    int result = quickSelect(arr, 0, n - 1, k);
    
    cout << "第" << k << "个最小元素是:" << result << endl;
    
    return 0;
}

上述代码中,`quickSelect`函数用于执行快速选择算法,其中`partition`函数用于进行数组的分割操作。在`main`函数中,我们定义了一个整型数组`arr`,并使用`quickSelect`函数寻找第k个最小元素。

希望对你有所帮助!如果还有其他问题,请随时向我提问。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-1-15 17:12:42 | 显示全部楼层    本楼为最佳答案   
快速选择算法是一种用于在无序数组中寻找第k个最小元素的算法。它的思想类似于快速排序,通过将数组分成两部分,其中一部分比pivot元素小,另一部分比pivot元素大。然后根据pivot元素所在的位置,判断第k个最小元素在哪一部分,并对相应的部分进行递归处理。

以下是一个使用快速选择算法寻找第k个最小元素的示例代码:
#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最右边的元素作为pivot
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

int quickSelect(int arr[], int low, int high, int k) {
    if (low == high) {
        return arr[low];
    }
    
    int pivotIndex = partition(arr, low, high);
    int rank = pivotIndex - low + 1;
    
    if (rank == k) {
        return arr[pivotIndex];
    } else if (rank < k) {
        return quickSelect(arr, pivotIndex + 1, high, k - rank);
    } else {
        return quickSelect(arr, low, pivotIndex - 1, k);
    }
}

int main() {
    int arr[] = {3, 1, 5, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;  // 寻找第2个最小元素
    
    int result = quickSelect(arr, 0, n - 1, k);
    
    cout << "第" << k << "个最小元素是:" << result << endl;
    
    return 0;
}

上述代码中,`quickSelect`函数用于执行快速选择算法,其中`partition`函数用于进行数组的分割操作。在`main`函数中,我们定义了一个整型数组`arr`,并使用`quickSelect`函数寻找第k个最小元素。

希望对你有所帮助!如果还有其他问题,请随时向我提问。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-21 18:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表