首页 > 试题广场 >

中位数

[编程题]中位数

热度指数：5923 时间限制：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 2 3 4，那么median数的下标为(4 - 1)/2 = 1, median数为2。加一个数字就可以了。

示例2

输入

3 4
1 2 3

输出

说明

样例二中，加入4 5 6 7，得到1 2 3 4 5 6 7，median数为4。最少加4个数字。

算法知识视频讲解

Python

ElonB

""""
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)