首页 > 试题广场 >

中位数

[编程题]中位数
  • 热度指数：5873 时间限制：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个数字。
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 18:56:21
题解： 考察点： 思维，数形结合 解法： 题目中要求的是让成为新数列的中位数，则说明把新数列按照从小到大顺序排序后，要正好处于的位置，于是采用数形结合的思想来解决此问题最为简单。首先统计原数组中小于的元素个数，大于的元素个数，等于的元素个数。于是会出现有下图种情况： 如左边所示，若的元素个数多于 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客379139307号
发表于 2020-03-15 18:29:01
while True: try: a,b=map(int,input().split()) s1 = list(map(int,input().split())) if b not in s1: flag = 1 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 贪心 数组 Momenta 模拟 2019 查找 Java工程师
来自：Momenta2019...
上传者：小小
难度：
18条回答 9302浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号