Python入门习题（18）——CCF CSP认证考试真题：中间数

问题描述

试题编号： 201612-1
试题名称： 中间数
时间限制： 1.0s
内存限制： 256.0MB

问题描述
　　在一个整数序列a1, a2, …, an中，如果存在某个数，大于它的整数数量等于小于它的整数数量，则称其为中间数。在一个序列中，可能存在多个下标不相同的中间数，这些中间数的值是相同的。
　　给定一个整数序列，请找出这个整数序列的中间数的值。
输入格式
　　输入的第一行包含了一个整数n，表示整数序列中数的个数。
　　第二行包含n个正整数，依次表示a1, a2, …, an。
输出格式
　　如果约定序列的中间数存在，则输出中间数的值，否则输出-1表示不存在中间数。
样例输入
6
2 6 5 6 3 5
样例输出
5
样例说明
　　比5小的数有2个，比5大的数也有2个。
样例输入
4
3 4 6 7
样例输出
-1
样例说明
　　在序列中的4个数都不满足中间数的定义。
样例输入
5
3 4 6 6 7
样例输出
-1
样例说明
　　在序列中的5个数都不满足中间数的定义。
评测用例规模与约定
　　对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ ai ≤ 1000。

解题思路

1. 对n个整数进行从小到大排序。
2. 要么中间数不存在，要么，中间数是排序后的序列中处于中间位置的整数。
3. 整数序列的中间位置是指：如果n为奇数，整数序列的中间位置是下标为$\lfloor n/2 \rfloor$⌊n/2⌋所在位置。如果n为偶数，那么处于中间位置有两个数，任选一个即可。这里以$\lfloor n/2 \rfloor$⌊n/2⌋所在位置视为中间位置。约定：序列下标从0开始。
4. 下面扼要证明下述结论成立：如果存在中间数，那么中间数是排序后的序列中处于中间位置的整数。
   a. 假设中间数所在位置是中间位置之前，那么必有中间数等于中间位置的整数。反证法证明如下：假定中间数不等于中间位置的整数，则有中间数小于中间位置的整数，因为中间数所在位置左边的整数数目小于$\lfloor n/2 \rfloor$⌊n/2⌋，这意味着，小于中间数的整数个数小于$\lfloor n/2 \rfloor$⌊n/2⌋。另一方面，中间位置及其右边的整数都大于中间数，所以大于中间数的整数数目大于等于$\lfloor n/2 \rfloor$⌊n/2⌋。因此，中间数小于中间位置的整数的结论不成立。
   b. 假设中间数所在位置是中间位置之后，证明方法类似，不再赘述。

参考答案

n = int(input())
nums = [int(s) for s in input().split()]  #列表推导式
nums.sort()  #从小到大排序
index_mid = n // 2  #中间位置
mid = nums[index_mid]  #有中间数的话，mid是中间数
count_less = 0  #存小于mid的整数个数
for i in range(0, index_mid):
    if nums[i] < mid:
        count_less += 1

count_larger = 0  #存大于mid的整数个数
for i in range(index_mid + 1, n):
    if nums[i] > mid:
        count_larger += 1

if count_less == count_larger:
    print(mid)
else:
    print(-1)

测试用例

除了题目描述中给出的样例输入-样例输出对，有必要针对以下情形构造测试用例来验证程序的正确性。

1. 情形1： n=1
   样例输入：
   1
   5
   样例输出：
   5
2. 情形2： 奇数个整数，全部相等，意味着小于中间数的个数为0，大于中间数的个数为0。
   样例输入：
   3
   5 5 5
   样例输出：
   5
3. 情形3： 奇数个整数，存在中间数。
   样例输入：
   5
   5 2 3 6 7
   样例输出：
   5

小结

1. 解答本题的关键是掌握以下数学结论：要么中间数不存在，要么，中间数是排序后的序列中处于中间位置的整数。基于此结论，解题思路和代码变得简洁明了。
2. 要验证解答的正确性，有必要针对各种情形构造测试用例。对于CCF软件能力认证考试而言，这一点尤为关键，因为在考试期间，考试系统不提供对了还是错了的反馈。你要靠自己构造测试用例来验证解答的正确性。