首页 > 试题广场 >

中位数

[编程题]中位数

热度指数：14020 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

中位数定义：一组数据按从小到大的顺序依次排列，处在中间位置的一个数（或最中间两个数据的平均数）. 给出一组无序整数，求出中位数，如果求最中间两个数的平均数，向下取整即可（不需要使用浮点数）

输入描述:

该程序包含多组测试数据，每一组测试数据的第一行为N，代表该组测试数据包含的数据个数，1<=N<=10000.
接着N行为N个数据的输入，N=0时结束输入

输出描述:

输出中位数，每一组测试数据输出一行

示例1

输入

输出

25
40
2

算法知识视频讲解

C/C++

forestjylee

//借助快排思路，找到中位数就立刻返回，无需全部排序~
#include<iostream>
(720)#include<vector>
using namespace std;

int partition(vector<int> &arr, int left, int right) {
    int mid_val = arr[left];
    while(left < right) {
        while(left < right && arr[right] >= mid_val) --right;
        arr[left] = arr[right];
        while(left < right && arr[left] <= mid_val) ++left;
        arr[right] = arr[left];
    }
    arr[left] = mid_val;
    return left;
}

void qS(vector<int> &arr, int left, int right, int mid_index, int mid_p1_index, bool &m1, bool &m2) {
    if(m1 && m2) return;
    if(left < right) {
        int mid=partition(arr, left, right);
        if(mid_index == mid) m1=true;
        else if(mid_p1_index == mid) m2=true; 
        qS(arr, left, mid-1, mid_index, mid_p1_index, m1, m2);
        qS(arr, mid+1, right, mid_index, mid_p1_index, m1, m2);
    }
}


int main() {
    int n;
    while(cin>>n) {
        vector<int> arr(n, 0);
        for(int i=0; i<n; ++i) cin>>arr[i];
        int mid_index=(n-1)/2;
        bool m1=false, m2=false;
        qS(arr, 0, n-1, mid_index, mid_index+1, m1, m2);
        if(n&1) cout<<arr[mid_index]<<endl;
        else cout<<(arr[mid_index]+arr[mid_index+1])/2<<endl;
    }
}

发表于 2020-04-30 12:11:03 回复(0)

C/C++

YhX.

#include<stdio.h>
int main()
{
    int n,i,j,t,a[10000];
    scanf("%d",&n); //1.输入
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n-1;i++)//2.排序
        for(j=0;j<n-1-i;j++)
            if(a[j]>a[j+1])
            {//交换
                t=a[j];a[j]=a[j+1];a[j+1]=t;
            }
    if(n%2==0)//证明是偶数,取平均值      //3.计算中位数
        printf("%d\n",(a[n/2]+a[n/2-1])/2);
    else
        printf("%d",a[n/2]);
}

发表于 2020-03-31 17:33:47 回复(0)

Java

LHC0512

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i]=scanner.nextInt();
            Arrays.sort(a);
            int len =a.length;
            if (len%2==0) System.out.println((a[len/2-1]+a[len/2])/2);
            else System.out.println(a[(len-1)/2]);
        }
    }
}

发表于 2020-03-18 17:29:40 回复(0)

C/C++

牛客480180948号

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){ 
	int n;
	while(cin>>n && n!=0){
		vector<int> vec(n);
		for(auto& a:vec)
			cin>>a;

		if(n%2==0){
			int a = n/2;
			int b = a-1;
			nth_element(vec.begin(),vec.begin()+b,vec.end());
			int el1 = vec[b];
			nth_element(vec.begin()+b,vec.begin()+a,vec.end());
			int el2 = vec[a];
			cout<<(el1+el2)/2<<endl;
		}else{
			int a= n/2;
			nth_element(vec.begin(),vec.begin()+a,vec.end());
			int el2 = vec[a];
			cout<<el2<<endl;
		}
	}
	return 0;
}

不需要排序全部，用快速排序的划分思想。

编辑于 2020-02-27 11:29:16 回复(0)

C/C++

算法小屁孩

#include<bits/stdc++.h>
int a[10001];
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)!=EOF && n!=0){
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        if(n&1) printf("%d\n",a[n/2]);
        else printf("%d\n",(a[n/2]+a[n/2-1])/2);
    }
}

发表于 2019-03-07 14:47:25 回复(0)

一叶之秋~

根据快排的思路来做

题目简化为求某个数组的最中间的两个数，然后根据快排的思路进行排除即可，相对于快排大大减少了比较的次数，代码如下：

import java.util.*;
public class Main{
    // 利用快排的思路寻找一个数组中第target大的数
    private static int getTarget(int[] data, int target){
        int mid=data[0], l=0, r=data.length-1;
        while(l < r){
            while(l < r && data[r] > mid) 
                r--;
            if(l < r)
                data[l++] = data[r];
            while(l < r && data[l] < mid) 
                l++;
            if(l < r)
                data[r--] = data[l];
        }
        data[l] = mid;

        if(l+1 == target)
            return data[l];
        else if(l+1 < target)
            return getTarget(Arrays.copyOfRange(data, l+1, data.length), target-(l+1));
        else
            return getTarget(Arrays.copyOfRange(data, 0, l), target);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            if(n == 0)
                break;
            int[] data = new int[n];
            for(int i=0; i<n; i++)
                data[i] = sc.nextInt();
            // 寻找一个数组中最中间的两个数
            int mid1 = (data.length+1)/2;
            int mid2 = (data.length+2)/2;
            System.out.println((getTarget(data, mid1)+getTarget(data, mid2))/2);
        }
        sc.close();
    }
}

发表于 2019-03-04 20:42:20 回复(0)

Python

TimeMac

try:
    while True:
        num = int(input())
        mouses = []
        for i in range(num):
            mouses.append(int(input()))
        mouses.sort()
        if num % 2 == 1:
            print(mouses[num//2])
        else:
            print((mouses[num//2]+mouses[num//2-1])//2)
except Exception:
    pass

编辑于 2018-10-08 22:38:17 回复(0)

♪Hippo

不知道为啥，把不为0的条件放到while括号里当参数会抛异常……Eclipse里调试的时候没问题，这么写就对了：

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt())
        {
            int n = sc.nextInt();
            if(n == 0)
                break;
            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = sc.nextInt();
            Arrays.sort(arr);
            if ((n & 1) == 1)
                System.out.println(arr[(n - 1) / 2]);
            else
                System.out.println((arr[n / 2] + arr[n / 2 - 1] ) / 2);
        }
        sc.close();
    }

}

发表于 2018-08-02 21:22:26 回复(0)

263保洁小妹

我是把数组排序，然后再找出中位数。但这肯定不是最优算法，因为找到中位数不需要数组全部有序，只需要中间的那一两个数在最终位置即可。我想到了快速排序中的partition操作，不过枢轴的位置似乎并不能确定？

#include <stdio.h>
#include <algorithm>
#define N 10000
using namespace std;

int main()
{
    int buf[N];
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        if(n<=0) break;
        for(int i=0; i<n; i++)
        {
            scanf("%d", &buf[i]);
        }
        sort(buf, buf+n);
        int mid=(n-1)/2;
        if(n%2==1) printf("%d\n", buf[mid]);
        else printf("%d\n", (buf[mid]+buf[mid+1])/2);
    }
    return 0;
}

发表于 2018-02-22 08:09:06 回复(3)

Python

华科平凡

python解法。不要忘了要对数组排序~



while True:
    try:
        a,res=int(input()),[]
        if a!=0:
            for i in range(a):
                res.append(int(input()))
            res.sort()
            resLen=len(res)
            print(res[resLen//2] if resLen%2==1 else (res[resLen//2]+res[resLen//2-1])//2)
    except:
        break

发表于 2017-10-06 13:58:55 回复(0)

C/C++

譕訫QAQ

输入到数组然后使用sort()函数排序根据n是奇数还是偶数直接算中间两个的平均值或者直接输出对应的数组值就可以了

#include <iostream>

#include <stdio.h>
#include <algorithm>
using namespace std;
int main(void)
{
    int n,sum,i;
    while(cin>>n&&n!=0)
    {
        int a[n];
        for(i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        if(n%2==0)
            sum=(a[n/2]+a[n/2-1])/2;
        else
            sum=a[n/2];
        cout<<sum<<endl;
    }
    return 0;
}

发表于 2019-11-17 21:07:25 回复(0)

云彩上的乐章

这种题来算中等也太凑数了吧。。。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    vector<int> num;
    int n;cin>>n;
    for(int i=0;i<n;++i){
        int number;cin>>number;
        num.push_back(number);
    }
    sort(num.begin(), num.end());
    if(num.size()%2!=0){
        cout<<num[num.size()/2];
    }
    else{
        cout<<(num[num.size()/2]+num[num.size()/2-1])/2;
    }
    return 0;
}

发表于 2021-03-05 11:04:26 回复(1)

小陈也只是想要一个实习罢了

用排序函数，要记住头文件，这里是简单的利用排序函数，还可以以自定义方式来使用，同时注意，排序为起始地址到起始地址+排序个数

#include<algorithm>
#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n==0)
            break;
        int* a=new int[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        if(n%2!=0)
            cout<<a[n/2]<<endl;
        else
            cout<<(a[n/2]+a[n/2-1])/2<<endl;
        delete []a;
    }
}

发表于 2019-02-06 22:25:30 回复(2)

Python3

chong_0428

def bubble(a):
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j+1]:
                t = a[j]
                a[j] = a[j+1]
                a[j+1] = t
    return a

def mid(a):
    a = bubble(a)
    # print(a)
    if len(a) % 2 == 0:
        i1 = int(len(a) / 2)
        i2 = int(len(a) / 2) - 1
        m = (a[i1] + a[i2]) / 2
    else:
        i = int(len(a) / 2)
        m = a[i]
    return int(m)


while True:
    try:
        arr = []
        n = int(input())
        for _ in range(n):
            a = int(input())
            arr.append(a)
        res = mid(arr)
        print(res)
    except:
        break

编辑于 2024-03-11 12:26:26 回复(0)

C++

sweetsora

std::nth_element

编辑于 2024-03-03 10:10:45 回复(0)

C++

无问西东gmy

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        vector<int>arr(n);
        for (auto& i : arr) {
            cin >> i;
        }
        sort(arr.begin(), arr.end());
        cout << (n % 2 == 1 ?
                 arr[(n - 1) / 2] :
                 (arr[(n - 1) / 2] + arr[(n + 1) / 2]) / 2)
             << endl;
    }
    return 0;
}

发表于 2024-01-30 17:23:31 回复(0)

希望奇迹发生的安迪很刻苦

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int a[N];

int main()

{

int n;

while(cin>>n&&n!=0)

{

for(int i=0;i<n;i++) cin>>a[i];

sort(a,a+n);

if(n%2!=0) cout<<a[n/2]<<endl;

else cout<<(a[n/2]+a[n/2-1])/2<<endl;

}

编辑于 2024-01-05 12:49:19 回复(0)

C++

Edward王

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        if(n==0) break;
        int arr[n];
        for(int i = 0; i < n; ++i){
            scanf("%d",&arr[i]);
        }
        //1.升序排序
        sort(arr,arr+n); 
        //2.找中位数
        if(n%2 == 1){ //n为奇数
            printf("%d\n",arr[n/2]);//arr[n/2]为中位数
        }else{ //n为偶数
            printf("%d\n",(arr[n/2]+arr[n/2-1])/2);
        }
    }
    return 0;
}

发表于 2023-03-23 14:19:43 回复(0)

C++

纯划水混子

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n,a[10020];
    int res;
    while(cin>>n&&n!=0){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        sort(a,a+n);//排序
        if(n%2==0){//n为偶数，则取中间两个数的平均数
            res=(a[n/2]+a[n/2-1])/2;
        }
        else{//n为奇数，则取中间的数
            res=a[n/2];
        }

        printf("%d\n",res);
    }
}

发表于 2023-03-20 09:39:10 回复(0)

C++

lyw菌

//知道sort后这题就简单多了，而且还是O(Nlog2N)的复杂度

#include "stdio.h"

#include "algorithm"

using namespace std;

int main(){

int N;int num[10001];

while (scanf("%d",&N)!=EOF) {

if(N == 0)

return 0;

for (int i =0; i<N; ++i) {

scanf("%d",num+i);

}

sort(num,num+N);

if(N%2 != 0)

printf("%d\n",num[N/2]);

else{

printf("%d\n",(num[N/2]+num[N/2-1])/2);

}

发表于 2023-03-07 17:49:15 回复(0)

提交观点

问题信息

数组排序

难度：

96条回答 48收藏 14742浏览

通过挑战的用户

查看代码

Gossen_

2023-03-12 21:38:35
牛客54314...

2023-02-24 16:57:25
cwz110117

2022-10-17 22:37:21
dearearing

2022-10-01 16:24:27
牛客30525...

2022-09-16 17:19:49

中位数

输入描述:

输出描述:

输入

输出

python解法。不要忘了要对数组排序~

问题信息

热门推荐

通过挑战的用户

相关试题