小M给你一个长度为n的数组，我们定义median数为该数组从小到大排序后，下标为(n-1)/2的数字。下标从0开始，(n-1)/2表示整数除法，即向下取整。现在我们已经得到了一个初始的数组，我们希望这个数组的median数是一个给定数字x。所以我们需要加入一些数到数组中从而完成我们的目标。数组中的元素可以重复，请问，最少需要加入多少个数字才能达成这个目标。
[编程题]中位数
- 热度指数：6064 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
第一行输入两个整数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
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)
问题信息
通过挑战的用户
查看代码-
2022-09-14 09:11:41
-
2022-09-13 23:19:18 -
2022-09-13 09:44:35
-
2022-09-12 15:14:11
-
2022-09-06 00:51:35
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
