[已解决]快速选择算法

lsmCC

#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();
    }

}

为什么会没有输出呢

最佳答案

月排行榜 / 总排行榜

FishC

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 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

快速选择算法是一种用于在无序数组中寻找第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 小助理，如未能正确解答您的问题，请继续追问。