首页 > 试题广场 >

中位数

[编程题]中位数
  • 热度指数:5858 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

M给你一个长度为n的数组,我们定义median数为该数组从小到大排序后,下标为(n-1)/2的数字。下标从0开始,(n-1)/2表示整数除法,即向下取整。现在我们已经得到了一个初始的数组,我们希望这个数组的median数是一个给定数字x。所以我们需要加入一些数到数组中从而完成我们的目标。数组中的元素可以重复,请问,最少需要加入多少个数字才能达成这个目标。


输入描述:
第一行输入两个整数n x (1 <= n <= 500, 1 <= x <= 10^5)。

接下来一行有n个正整数表示初始的数组,用空格分开,范围是[1, 10^5]。


输出描述:
输出需要加入最少的元素个数才能够使得新数组的median数成为x。
示例1

输入

3 2
2 3 4

输出

1

说明

样例一中,加入1,得到1 2 3 4,那么median数的下标为(4 - 1)/2 = 1, median数为2。加一个数字就可以了。
示例2

输入

3 4
1 2 3

输出

4

说明

样例二中,加入4 5 6 7,得到1 2 3 4 5 6 7,median数为4。最少加4个数字。
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
                //至少添加的次数,即结果
        int res=0;
        int nums=sc.nextInt();
        int target=sc.nextInt();
                //小于中位数的个数
        int min=0;
                //大于中位数的个数
        int max=0;
                //等于中位数的个数
        int same=0;
                //中位数是否存在
        boolean isExist=false;
        for(int i=0;i<nums;i++){
            int temp=sc.nextInt();
            if(temp>target){
                max++;
               
            }
            else if(temp<target){
                min++;
            }
            else if(temp==target){
                              //中位数已存在,保存多出来的个数
                  if(isExist){
                    same++;
                  }else{
                isExist=true;}
            }
        }
                //如果不存在中位数,添加中位数,次数加一
        if(isExist==false) res++;
                //如果max大于min的时候,记录差值为dif
//如果dif大于same时,中位数的左边要添加dif-same-1个数组
//举例:中位数为3  1 2 3 3 3 4 4 4 4 4 4 4
//因为中位数永远位于左边,所以可以少添加一个 
//如果dif小于same时,添加0
//举例: 中位数为3  1 2 2 3 3 3 3 4 4 4 4
        if(max>min){
            int dif=max-min;
            dif=dif>same?dif-same-1:0;
            res+=(dif);
        }
                //如果min大于max情况的时候 ,记录差值为dif
//如果dif大于same时 中位数的右边要添加dif-same个数字:举例 中位数为3  1 2 2 2 2 3 3 4 4 
                //如果dif小于等于same时 添加0:举例 中位数为3  1 2 2 2 3 3 3 3 4 
        else if(min>max){
            int dif=min-max;
            dif=dif>same?dif-same:0;
            res+=(dif);
        }
        
        System.out.print(res);
    }
}

发表于 2019-09-13 14:45:57 回复(0)
""""
n最大为500,暴力尝试
"""


def median(a, x):
    ans = 0
    if a[(len(a) - 1) // 2] == x:
        ans = 0
    while a[(len(a) - 1) // 2] > x:
        a.insert(0, a[0])
        ans += 1
    while a[(len(a) - 1) // 2] < x:
        a.append(a[-1])
        ans += 1
    return ans


if __name__ == "__main__":
    n, x = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    if x in a:
        a.sort()
        ans = median(a, x)
    else:
        a.append(x)
        a.sort()
        ans = median(a, x) + 1
    print(ans)

发表于 2019-07-16 21:28:52 回复(0)
#include<iostream>

using namespace std;

int main(){
    int n,x;
    cin>>n>>x;
    int a[n];
    int m = (n-1)/2, left=0, right=0, count=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]==x)
            count++;
        else if(a[i]<x)
            left++;
        else
            right++;
    }
    if(left<=m){//排序后有x在m的左边或者x位置上
        if(m<n-right)//有x恰好在m位置上
            cout<<0<<endl;
        else//需要在最右边的x上往左边添数
            //最右边x的右边的数字有right个,它的左边有left+count-1个
            //我们需要保证补数字后,它左边的数字比右边刚好少一个
            //即add=right-(left+count-1)-1==right-left-count
            cout<<right-left-count<<endl;
    }else{//排序后,x在m的右边,这个时候往最左边的x的右边补数后,最左边的x左边的数和右边的数应该相等
        //左边的数是left个,右边的数是right+count-1个
        cout<<left-(right+count-1)<<endl;
    }
        
    return 0;
}
我给大佬的代码自己过了一遍,和大家分享。
发表于 2019-08-23 17:16:07 回复(0)
if __name__=='__main__': 
    n,x = input().split()
    n = int(n)
    x = int(x)
    arr = [int(x) for x in input().split()]
    # count
    left = right = same = 0
    for i in arr:
        if i > x:
            right += 1
        elif i < x:
            left += 1
        else:
            same += 1
    # cal 
    if right > left:
        need = max(right - left - same,0)
    elif left > right:
        need = max(left - right - same + 1,0)
    else:
        if same == 0:
            need = 1
        else:
            need = 0
    print(need)

编辑于 2019-09-12 17:25:20 回复(0)
#include<bits/stdc++.h>
using namespace std;

int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,x;
	cin>>n>>x;
	int a[n];
	int m=(n-1)/2,l=0,r=0,e=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i]==x)
			e++;//记录数组中等于给定值的个数 
		else if(a[i]<x)
			l++;//数组中给定值左边的个数 
		else
			r++;//数组中给定值右边的个数 
	}
	
	if(l<=m){	//给定值左边的个数 小于 给定值的位置;即左边的个数不够 
		if(r<n-m)	//给定值右边的个数不够
			cout<<0<<endl;	//数组中,给定值左边的不够,右边的也不够,所以中间的一些值都是给定值;故不需要添加数字
		else 	//右边的个数多,所以左边添加个数 
			cout<< r-l-e<<endl;	 // 因为需要左边添加个数,所以将给定值当做左边的。这样可以尽可能少的添加 
	}else{	//左边的个数多 
		cout<<l-r-e+1<<endl;  //需要添加右边的,所以将等于给定值的数当做右边的;同时由于m的位置是向下取整,因此右边需要多加1 
	} 
	
	return 0; 
	
} 


发表于 2019-08-20 16:04:26 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,res=0;
    cin>>n>>x;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
        cin>>nums[i];
    int flag = 1;
    for(int i=0;i<n;i++)
        if(nums[i] == x)
            flag = 0;
    if(flag)
    {
        nums.push_back(x);
        n++;
    }
    sort(nums.begin(),nums.end());
    int left = -1;
    int right = -1;
    for(int i=0;i<n;i++)
    {
        if(x == nums[i])
        {
            if(left == -1)
            {
                left = i;
                right = i;
            }
            else
                right = i;
        }
    }
    int target = (n-1)/2;
    if(target < left)
        while(left > (n-1 + res)/2)
            res++;
    else if(target > right)
        while(right + res < (n-1 + res)/2)
            res++;
    cout<<res+flag<<endl;
    return 0;
}

发表于 2019-07-09 20:25:32 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x;
    cin>>n>>x;
    int a[n];
    int m = (n-1)/2, l=0, r=0, e=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]==x)
            e++;
        else if(a[i]<x)
            l++;
        else
            r++;
    }
    if(l<=m){
        if(r<n-m)
            cout<<0<<endl;
        else
            cout<<r-l-e<<endl;
    }else{
        cout<<l+1-r-e<<endl;
    }
       
    return 0;
}

编辑于 2019-08-14 07:57:05 回复(1)
#include<stdio.h>

#define maxn 1000

int a[maxn];

// 快速排序函数
void quickSort(int l, int r) {
  if (l >= r) {   // 递归结束条件:区间只有一个元素或区间为空
    return;
  }
  int i = l, j = r, pivot = a[l]; // 定义左右指针和枢轴元素
  while (i < j) { // 左右指针相遇时退出循环
    while (i < j &&
           a[j] >= pivot) {    // 右指针向左移动,找到第一个小于枢轴元素的元素
      j--;
    }
    a[i] = a[j];    // 将该元素赋值给左指针所在位置
    while (i < j &&
           a[i] <= pivot) {    // 左指针向右移动,找到第一个大于枢轴元素的元素
      i++;
    }
    a[j] = a[i];    // 将该元素赋值给右指针所在位置
  }
  a[i] = pivot;   // 将枢轴元素放到最终正确的位置上
  quickSort(l, i - 1);    // 对左半部分区间递归进行快排
  quickSort(i + 1, r);    // 对右半部分区间递归进行快排
}

int main() {
  int n, x, i;
  scanf("%d%d", &n, &x);  // 输入数组长度和要插入的元素
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]); // 输入原始数组
  }

  quickSort(0, n - 1);    // 对原始数组进行排序

  int cnt = 0;    // 记录插入次数
  while (a[(n - 1) / 2] !=
         x) {   // 当中位数不等于要插入的元素时循环
    if (a[(n - 1) / 2] > x) {  // 如果中位数大于要插入的元素
      for (int k = n; k > (n + 1) / 2;
           k--) { // 将中位数及其右边的元素全部向右移动一位
        a[k] = a[k - 1];
      }
      a[(n + 1) / 2] = x;    // 将要插入的元素放到新的中间位置
    } else {    // 如果中位数小于要插入的元素
      for (int k = n; k >= (n + 1) / 2;
           k--) {    // 将中位数及其右边的元素全部向右移动一位
        a[k] = a[k - 1];
      }
      a[(n - 1) / 2] = x;    // 将要插入的元素放到新的中间位置
    }
    cnt++;  // 插入次数加1
    n++;    // 数组长度加1
    quickSort(0, n - 1);    // 对新的数组进行排序
  }

  printf("%d\n", cnt);

  return 0;
}

发表于 2023-11-21 16:25:01 回复(0)
import sys
n, x = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
l_x, r_x, n_x = 0, 0, 0
for ai in a:
    if ai < x:
        l_x += 1
    elif ai > x:
        r_x += 1
    else:
        n_x += 1
if l_x >= r_x:
    res = max(0, l_x - r_x - n_x + 1)
else: 
    res = max(0, r_x - l_x - n_x)
print(res)

发表于 2020-04-13 23:09:51 回复(0)
时间太长了,我是用快速排序的那种partition方法,先分以下,然后再去判断怎么加。
//让我想到了快排一次的partition,按照 x partition一下吗
//存在的问题:数组里允许有重复数字吗?可以哦,
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();
        int nums[] = new int[n+1];
        int index = -1;
        int count_x = 0;
        for(int i=0;i<n;++i){
            nums[i]=scanner.nextInt();
            if(nums[i]==x) {
                count_x++;
                index=i;
            }
        }
        scanner.close();
        if(count_x==0){
            //没有x加一个进来
            nums[n]=nums[0];
            nums[0]=x;
            index=0;
            count_x=1;            
            System.out.println(howManyToInsert(nums,n+1,x,index,count_x)+1);
        }
        else {
            
            if(index!=0){
                //做一个处理
                int temp = nums[0];
                nums[0]=nums[index];
                nums[index]=temp;
            }
            System.out.println(howManyToInsert(nums,n,x,index,count_x));
        }
    }
    private static int howManyToInsert(int nums[],int len,int x,int index,int count_x){
        //首先按照x进行一次partition
        //记录x的个数
        //如果没有x怎么办?
        int howMany = 0;
        /*if(count_x==0){
            //没有x;加一个进来 O(n)时间复杂度O(n)空间复杂度
            int temp[] = new int[len+1];
            temp[0]=x;
            for(int i=1;i<=len;++i){
                temp[i]=nums[i-1];
            }
            nums=temp;
            temp=null;
            howMany+=1;
            count_x+=1;
            index=0;
        }*///这种想法实在太慢了
        int low = 0;
        int high = len-1;
        while(low<high){
            while(low<high&&nums[high]>=x){
                high--;
            }
            nums[low]=nums[high];
            while(low<high&&nums[low]<x){
                low++;
            }
            nums[high]=nums[low];
        }
        nums[low]=x;
        //low就是现在x的第一个位置
        int median = (len-1)/2;
        if(low<median){
            while(low+count_x-1<(len+howMany-1)/2){
                //这种情况下怎么添加更好呢?
                //只要有添加,右边的每两次增长1
                //a.添加大于x肯定不行
                //b.添加小于x:low肯定要增加1每次
                //c.添加等于x:coung_x肯定每次增加1
                //所以b和c是一样的
                howMany+=1;
                low++;
            }
            return howMany;
        }
        else if(low>median){
            while(low>(len+howMany-1)/2){
                //只要有添加,右边没两次增加1
                //a.添加小于x的,low每次增1
                //b.添加大于x的,low每次不变
                //c.添加等于x的,low不变
                //所以我肯定要使得low减少或者不变的
                howMany++;
            }
            return howMany;
        }
        return howMany;
    }
}


发表于 2020-04-09 18:04:44 回复(1)
//统计出x左边的数,右边的数,以及等于x的数
//运用数学知识,很容易求得结果
//注意,若在左边插入时,总数应该为偶数,插入的数最小
//若在右边插入时,总数应该为奇数,插入的数最小
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

int InsertNum(vector <int> &v,int L,int x){
    int right=0,left=0,eql=0;
    for(int i=0;i<L;i++){
        if(v[i]==x)eql++;
        if(v[i]<x)left++;
        if(v[i]>x)right++;
    }
    if(left<right+eql){
        if(left+eql>=right)return 0;
        else {//在左边添加 总数应该为偶数;
            return 2*right-L;
        }
    }else{//在右边添加应该总数为奇数;
        return 2*left-L+1;
    }
}
int main(){
    int n;
    int x;
    vector<int>v;
    cin>>n;
    cin>>x;
    int temp=n;
    while(temp--){
        int a;
        cin>>a;
        v.push_back(a);
    }
    cout<<InsertNum(v,n,x);
    return 0;
}


发表于 2020-02-17 21:18:26 回复(0)
int median(int n, unsigned int x, std::vector<unsigned int> arr) {
    int less = 0, high = 0, equal = 0;    //分别表示array中数与x比较的个数——小,大,等
    for(int i = 0; i < n; i++)
    {
        if(arr[i] == x)
        {
            ++equal;
        }
        else if(arr[i] < x)
        {
            ++less;
        }
        else
        {
            ++high;
        }
    }

    int add = 0;                        //需要增加的数的个数

    // 下面通过左边的数和右边的数进行抵消来判断增加的数
    if(less == high)
    {
        if(equal == 0)
        {
            add = 1;
        }
        else
        {
            add = 0;
        }
    }
    else if(less < high)
    {
        if((high - less) < equal)
        {
            add = 0;
        }
        else
        {
            add = high - less - equal;
        }
    }
    else
    {
        if((less - high) < equal)
        {
            add = 0;
        }
        else
        {
            add = less - high - equal + 1;
        }
    }

    return add;
}

本题核心的思路是,无论中位数x在数组的什么位置,目的都是保证x在数组的中间位置,那么就可以考虑将左右两边的原有数据进行抵消,剩下的无论是左边的数据还是右边的数据,只需要添加相对边的数据个数即可。需要注意的是,数组中的数据是可以重复的,所以数组中含有多个中位数x是需要考虑的情况,但好在取整,所以无论是整偶数个数的x还是奇数个数的x都可以将指定x视为相同值中的中位数。
发表于 2020-02-10 19:45:41 回复(0)
#include<bits/stdc++.h> 
#include <algorithm>
using namespace std;
int main(){
    int a[1000];
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        int f=1000,l=0,flag=0,ans=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            if(a[i]==m)flag++;
        }
//判断是否存在,不存在就插入一个
        if(flag==0){
            a[n]=m;
            n++;
            ans++;
        }
        sort(a, a + n);
        for(int i=0;i<n;i++){
            if(a[i]==m){
                if(f>i)f=i;
               if(l<i)l=i;
            }
        }
         int mid=(n-1)/2;
        if(a[mid]==m){
            printf("%d\n",0+ans);
        }
        else if(a[mid]>m){
            printf("%d\n",n-1-2*l-1+ans);
        }
        else{
            printf("%d\n",2*f+1-n+ans);
        }
        
    }
    return 0;
}

发表于 2019-09-20 14:44:34 回复(0)
import java.util.*;

public class Main {

	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] array=new int[n];
        int left=0;
        int right=0;
        int xcount=0;
        int result=0;
        for(int i=0;i<n;i++)
        {
            int num = sc.nextInt();
            if(num==x)
                xcount++;
            else if(num<x)
                left++;
            else if(num>x)
                right++;
        }
        if(xcount==0)
        {
            xcount++;
            result++;
        }
        if(left+xcount<right)
        {
            result+=(right-(left+xcount));
            System.out.println(result);
            return;
        }
        else if(left>=right+xcount)
        {
            result+=(left-(right+xcount)+1);
            System.out.println(result);
            return;
        }
        else
        {
            System.out.println(result);
            return;
        }
	}
}

发表于 2019-08-30 12:53:29 回复(0)
不知道为啥,用了楼上的一些代码跑不过,就是计数后判断那一块,然后就自己想了,感觉我这个看起来逻辑还是比较清楚,虽然不够简洁

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n, median;
    cin>>n>>median;
    
    int index = (n-1)/2;
    int less = 0, high = 0, equal = 0;
    
    vector<unsigned int> nums;
    unsigned int temp = 0;
    for(int i=0; i<n; i++){
        cin>>temp;
        nums.push_back(temp);
        if(temp==median){
            equal++;
        }else{
            if(temp<median){
                less++;
            }else{
                high++;
            }
        }
    }
    
    if(less==high){
    //如果小的数和大的数的数量相同,此时要判断median是否在输入序列中
        if(equal>0)
            cout<<0;
        else
            cout<<1;
    }else{
        if(less<high){
            //如果小的数小于大的数,首先相互抵消,还剩high-less个数
            if(high-less<equal){
                //注意隐含了equal>0这个条件(因为high-less一定是大于0的)
                cout<<0;
            }else{
                cout<<high-less-equal;
            }
        }else{
            if(less-high<equal){
                cout<<0;
            }else{
                cout<<less-high-equal+1;
            }
        }
    }
    
    return 0;
}

发表于 2019-08-22 17:44:24 回复(1)
import java.io.*;
import java.util.Arrays;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] line1=br.readLine().split(" ");
        int n=Integer.parseInt(line1[0]);
        int x=Integer.parseInt(line1[1]);
        String[] line2=br.readLine().split(" ");
        int[] nums=new int[n];
        int l=0,e=0,h=0;
        for(int i=0;i<n;i++){
            nums[i]=Integer.parseInt(line2[i]);
            if(nums[i]==x){
                e++;
            }else if(nums[i]<x){
                l++;
            }else{
                h++;
            }
        }
        if(l<=(n-1)/2 && (n-1)/2<=l+e-1){
            System.out.println(0);
        }else if(l>h){
            System.out.println(l-(h+e-1));
        }else if(l<h){
            System.out.println(h-(l+e-1)-1);
        }else{//用于解决l==h的部分
            System.out.println(1);
        }
    }
}
三向切分快速排序的变式
发表于 2019-08-19 20:46:55 回复(0)
import java.util.Scanner;
import java.util.Arrays;
//未考虑到中位数存在很多时,二分法查找不准
//解决方案,找到第一个和最后一个的位置,再分别计算需要添加的数量后取最少的。

//此方案是在输入数据时就事先找到位置。可以省去排序和查找的时间。
//计算结果时可以再优化,因为之前是根据二分查找的返回值计算的。
public class Main{
    public static void main(String[] args){
        //scan parameter
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int x = in.nextInt();
        int[] array = new int[num];
        int pos = -1, l = -1, h = -1;//l和h分别记录低位和高位位置
        for(int i = 0; i < num; i++){
            array[i] = in.nextInt();
            //此时就开始查找x的位置
            if(array[i] < x){
                pos = pos<0? pos-1: pos+1;
                l++;
                h++;
            } 
            if(array[i] == x){
                if(pos < 0){
                    l = h = pos = -pos-1;
                }else{
                    h++;
                }
            }
        }
        //function realize
        if(pos < 0){
            int temp = num+2*pos+2;
            System.out.println(temp > 0 ? temp : 1-temp);
        }else{
            int temp1 = num-2*l-1 > 0 ? num-2*l-1-1 : -(num-2*l-1);
            int temp2 = num-2*h-1 > 0 ? num-2*h-1-1 : -(num-2*h-1);
            System.out.println(temp1 < temp2 ? temp1 : temp2);
        }
    }
}

编辑于 2019-08-16 11:08:52 回复(0)
if __name__=='__main__':
    try:
        while True:
            s = input().strip()
            if s == '':
                break
            else:
                n, x = map(int, s.split())
                l = sorted(list(map(int, input().strip().split())))
                mid = -1
                if x in l:
                    for i in range(n):
                        if l[i] == x:
                            if abs(mid - (n-1) // 2) > abs(i - (n-1) // 2):
                                mid = i
                    left = mid
                    right = n - mid - 1
                    print(left - right if left >= right else right - left-1)
                else:
                    l.append(x)
                    l = sorted(l)
                    mid = l.index(x)
                    left = mid
                    right = n - mid
                    print(left-right+1 if left>=right else right-left)
    except:
        pass

发表于 2019-04-16 17:19:29 回复(0)