首页 > 代码库 > 线性求中位数 poj2388

线性求中位数 poj2388

2024-07-14 09:37:20   225人阅读

在做uva11300时，遇到了n < 1000 000的中位数，就看了一下线性求中位数。

和快排的思想很像，同理，线性求第k大数，算法如下：

①以某个数x将一段数组分成两部分，比x小的放在左边，比x大的放在右边

②如果x刚好是出于要找的位置的，直接返回

③如果在x的左边，则递归在x的右边找

④如果在x的右边，则递归在x的左边找

代码如下：

 1 /*=============================================================== 2 *   Copyright (C) 2014 All rights reserved. 3 *    4 *   File Name: poj2388.cpp 5 *   Author:sunshine 6 *   Created Time: 2014年07月28日 7 * 8 ================================================================*/ 9 #include <map>10 #include <queue>11 #include <stack>12 #include <math.h>13 #include <stdio.h>14 #include <string.h>15 #include <iostream>16 #include <algorithm>17 18 using namespace std;19 20 21 int find_mid(int arr[], int left, int right, int x){22     if(left >= right){23         return arr[left + x];24     }25     int mid = arr[left];26     int i = left;27     int j = right;28     while(i < j){29         while(i < j && arr[j] >= mid) j--;30         arr[i] = arr[j];31         while(i < j && arr[i] <= mid) i++;32         arr[j] = arr[i];33     }34     arr[j] = mid;35     if(i - left == x) return arr[i];36     if(i - left < x) return find_mid(arr, i + 1, right, x - (i - left + 1));37     else return find_mid(arr, left, i - 1, x);38 }39 40 int arr[10005];41 int main(){42     int n;43     while(scanf("%d", &n) != EOF){44         for(int i = 0;i < n;i ++){45             scanf("%d", &arr[i]);46         }47         printf("%d\n", find_mid(arr, 0, n-1, n / 2));48     }49     return 0;50 }
View Code

 


联系
我们