首页 > 代码库 > 线性求中位数 poj2388
线性求中位数 poj2388
在做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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。