【算法入门】排除异形基因 - Python 代码实现

【算法入门】排除异形基因 - Python 代码实现

比赛题目

时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 16MB，其他语言 32MB

描述

神舟号飞船在完成宇宙探险任务回到地球后，宇航员张三感觉身体不太舒服，去了医院检查，医生诊断结果：张三体内基因已被改变，原有人体基因序列中已经被渗入外星球不明异形生物基因，但可喜的是，这些异形基因都有一个共同的特征，就是该基因序号的平方除以7的余数都是1，要赶快清除掉，否则会危害整个人类。赶快行动吧。

输入描述

第一行是一个整数n（基因个数,3<=n<=200） 第二行是n个整数（张三的基因序列）

输出描述

去除异形基因后的正常序列，空格隔开

用例输入 1

4
6 2 8 12

用例输出 1

2 12

思路

遍历基因序列，对每个基因进行判断，如果基因序号的平方除以7的余数不是1，则将该基因添加到结果序列中。

具体实现步骤如下：

1. 读取输入的基因个数n。
2. 读取输入的n个基因序列。
3. 创建一个空的结果序列。
4. 遍历基因序列，对每个基因进行判断：
   • 计算基因序号的平方除以7的余数。
   • 如果余数不是1，则将该基因添加到结果序列中。
5. 输出结果序列，空格隔开。

代码如下：

n = int(input())  # 读取基因个数
genes = list(map(int, input().split()))  # 读取基因序列

result = []  # 结果序列

for gene in genes:
    if (gene ** 2) % 7 != 1:
        result.append(gene)

print(' '.join(map(str, result)))  # 输出结果序列，空格隔开

复杂度分析：

• 时间复杂度：O(n)，其中n为基因个数。
• 空间复杂度：O(m)，其中m为去除异形基因后的正常基因个数。