Python算法题解：寻找最优秀的实习生

题目描述:

蒜头君想招募实习生编写课程，收到了N份简历。为了选出最优秀的候选人，boss决定进行一个“随机”测试。他将从N份简历中随机抽取M份，然后查看剩余简历中最中间那一份，并认为这份简历的持有者最优秀。

你的任务是编写一个程序，帮助蒜头君预测boss最终会选中的简历ID。

输入格式:

第一行包含两个正整数N和M（1 ≤ M < N ≤ 1000），分别表示简历总数和boss抽取的简历数量。* 第二行包含M个正整数num_i（1 ≤ num_i ≤ 1000），表示boss每次抽取的简历编号（相对于剩余简历）。

输出格式:

输出一行，包含一个整数，表示boss认为最优秀的同学的简历ID。

解题思路:

我们可以使用列表模拟简历抽取的过程，并根据剩余简历数量确定中间位置的索引。

具体步骤:

读取输入的N和M。2. 读取输入的M个数字，存储到一个列表中。3. 创建一个包含1到N的id列表，代表所有简历。4. 遍历boss抽取的简历编号列表，根据编号从id列表中移除对应简历。5. 计算剩余简历数量，确定中间简历的索引。6. 输出中间简历的ID。

**代码实现:**pythonN, M = map(int, input().split())nums = list(map(int, input().split()))

ids = list(range(1, N+1))

for num in nums: ids.pop(num-1)

middle_index = (N - M) // 2middle_id = ids[middle_index]print(middle_id)

复杂度分析:

时间复杂度: 假设N为简历的数量，M为抽取的简历数量，遍历boss抽取的简历编号列表的时间复杂度为O(M)，剩余简历的数量为N-M，计算中间简历索引的时间复杂度为O(1)，因此总时间复杂度为O(M)。* 空间复杂度: 除了输入的N和M外，额外使用了一个列表存储boss抽取的简历编号，以及一个列表存储简历的ID，因此空间复杂度为O(N+M)。

示例:

输入:

5 22 4

输出:

解释:

初始简历ID为[1, 2, 3, 4, 5]。

最终剩余简历中，中间位置的简历ID为3。