[已解决]快速选择算法

lsmCC

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. typedef long long ll;
   
4. #define INF 0x3f3f3f3f
   
5. typedef pair<int,int>pii;
   
6. const int N=2e5+10;
   
7. // 用快速选择算法
   
8. int n,k;
   
9. int q[N];
   
10. int quick_sort(int l,int r,int k)
    
11. {
    
12.     if(l==r)return q[l];
    
13.     int x=q[l],i=l-1,j=i+1;
    
14.     while(i<j)
    
15.     {
    
16.         do i++;while(q[i]<x);
    
17.         do j--;while(q[j]>x);
    
18.         if(i<j)swap(q[i],q[j]);
    
19. 
    
20.     }
    
21.     int sl=j-l+1;// 左边区间有多少个数
    
22.     if(k<=sl)return quick_sort(l,j,k);
    
23.     return quick_sort(j+1,r,k-sl);
    
24. 
    
25. 
    
26. }
    
27. 
    
28. void solve()
    
29. {
    
30.     cin>>n>>k;
    
31.     for(int i=0;i<n;i++)
    
32.     {
    
33.         cin>>q[i];
    
34.     }
    
35.     cout<<quick_sort(0,n-1,k)<<endl;
    
36.    
    
37. 
    
38. }
    
39. int main()
    
40. {
    
41.     ios::sync_with_stdio(0);
    
42.     cin.tie(0);
    
43.     cout.tie(0);
    
44.     int t;
    
45.     t=1;
    
46.     while(t--)
    
47.     {
    
48.         solve();
    
49.     }
    
50. 
    
51. }

复制代码

为什么会没有输出呢

最佳答案

月排行榜 / 总排行榜

FishC

2024-1-15 17:12:42

快速选择算法是一种用于在无序数组中寻找第k个最小元素的算法。它的思想类似于快速排序，通过将数组分成两部分，其中一部分比pivot元素小，另一部分比pivot元素大。然后根据pivot元素所在的位置，判断第k个最小元素在哪一部分，并对相应的部分进行递归处理。

以下是一个使用快速选择算法寻找第k个最小元素的示例代码：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int partition(int arr[], int low, int high) {
   
5.     int pivot = arr[high];  // 选择最右边的元素作为pivot
   
6.     int i = low - 1;
   
7.    
   
8.     for (int j = low; j < high; j++) {
   
9.         if (arr[j] <= pivot) {
   
10.             i++;
    
11.             swap(arr[i], arr[j]);
    
12.         }
    
13.     }
    
14.     swap(arr[i + 1], arr[high]);
    
15.     return i + 1;
    
16. }
    
17. 
    
18. int quickSelect(int arr[], int low, int high, int k) {
    
19.     if (low == high) {
    
20.         return arr[low];
    
21.     }
    
22.    
    
23.     int pivotIndex = partition(arr, low, high);
    
24.     int rank = pivotIndex - low + 1;
    
25.    
    
26.     if (rank == k) {
    
27.         return arr[pivotIndex];
    
28.     } else if (rank < k) {
    
29.         return quickSelect(arr, pivotIndex + 1, high, k - rank);
    
30.     } else {
    
31.         return quickSelect(arr, low, pivotIndex - 1, k);
    
32.     }
    
33. }
    
34. 
    
35. int main() {
    
36.     int arr[] = {3, 1, 5, 2, 4};
    
37.     int n = sizeof(arr) / sizeof(arr[0]);
    
38.     int k = 2;  // 寻找第2个最小元素
    
39.    
    
40.     int result = quickSelect(arr, 0, n - 1, k);
    
41.    
    
42.     cout << "第" << k << "个最小元素是：" << result << endl;
    
43.    
    
44.     return 0;
    
45. }

复制代码

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

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

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

快速选择算法是一种用于在无序数组中寻找第k个最小元素的算法。它的思想类似于快速排序，通过将数组分成两部分，其中一部分比pivot元素小，另一部分比pivot元素大。然后根据pivot元素所在的位置，判断第k个最小元素在哪一部分，并对相应的部分进行递归处理。

以下是一个使用快速选择算法寻找第k个最小元素的示例代码：

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int partition(int arr[], int low, int high) {
   
5.     int pivot = arr[high];  // 选择最右边的元素作为pivot
   
6.     int i = low - 1;
   
7.    
   
8.     for (int j = low; j < high; j++) {
   
9.         if (arr[j] <= pivot) {
   
10.             i++;
    
11.             swap(arr[i], arr[j]);
    
12.         }
    
13.     }
    
14.     swap(arr[i + 1], arr[high]);
    
15.     return i + 1;
    
16. }
    
17. 
    
18. int quickSelect(int arr[], int low, int high, int k) {
    
19.     if (low == high) {
    
20.         return arr[low];
    
21.     }
    
22.    
    
23.     int pivotIndex = partition(arr, low, high);
    
24.     int rank = pivotIndex - low + 1;
    
25.    
    
26.     if (rank == k) {
    
27.         return arr[pivotIndex];
    
28.     } else if (rank < k) {
    
29.         return quickSelect(arr, pivotIndex + 1, high, k - rank);
    
30.     } else {
    
31.         return quickSelect(arr, low, pivotIndex - 1, k);
    
32.     }
    
33. }
    
34. 
    
35. int main() {
    
36.     int arr[] = {3, 1, 5, 2, 4};
    
37.     int n = sizeof(arr) / sizeof(arr[0]);
    
38.     int k = 2;  // 寻找第2个最小元素
    
39.    
    
40.     int result = quickSelect(arr, 0, n - 1, k);
    
41.    
    
42.     cout << "第" << k << "个最小元素是：" << result << endl;
    
43.    
    
44.     return 0;
    
45. }

复制代码

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

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

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。