Description
转座子指一段可以从原位上单独复制或断裂下来,环化后插入另一位点,并对其后的基因起调控作用的DNA序列,即转座子在基因序列中没有特定位置。已知某原核生物的某段基因中含有一个转座子。现给出多个个体相关基因序列(用连续正整数编号基因片段),设计程序找出转座子。
Input
第一行,一个数字n,表示相关基因序列所含有基因片段的个数。
第i(100>=i>=2)行,每行n个数字,表示第(i-1)个个体相关基因序列。
Output
一个数字,即转座子对应编号。若无法确定转座子,输出“-1”.
Sample Input 1
6
1 2 3 4 5 6
1 3 2 4 5 6
1 3 4 5 2 6
2 1 3 4 5 6
Sample Output 1
2
Sample Input 2
5
1 2 3 4 5
1 3 2 4 5
Sample Output 2
-1
Hint
对于样例1,基因片段1、3、4、5、6位置不变,2位置不确定,则转座子为2.
对于样例2,基因片段1、4、5位置不变,2、3位置不确定,则无法确定转座子为2或3.
对于100%的数据:n<=50,且基因片段编号均属于区间[1,n]且不重复.
# include<stdio.h>
/*Description
转座子指一段可以从原位上单独复制或断裂下来,环化后插入另一位点,
并对其后的基因起调控作用的DNA序列,即转座子在基因序列中没有特定位置。
已知某原核生物的某段基因中含有一个转座子。现给出多个个体相关基因序列(
用连续正整数编号基因片段),设计程序找出转座子。
Input
第一行,一个数字n,表示相关基因序列所含有基因片段的个数。
第i(100>=i>=2)行,每行n个数字,表示第(i-1)个个体相关基因序列。
Output
一个数字,即转座子对应编号。若无法确定转座子,输出“-1”.
Sample Input 1
6
1 2 3 4 5 6
1 3 2 4 5 6
1 3 4 5 2 6
2 1 3 4 5 6
Sample Output 1
2
Sample Input 2
5
1 2 3 4 5
1 3 2 4 5
Sample Output
-1
Hint
对于样例1,基因片段1、3、4、5、6位置不变,2位置不确定,则转座子为2.
对于样例2,基因片段1、4、5位置不变,2、3位置不确定,则无法确定转座子为2或3.
对于100%的数据:n<=50,且基因片段编号均属于区间[1,n]且不重复.*/
int main()//可以看出,。每一个序列只有一个转座子,所以各元素除转座子外
//位置变化只会是+1或-1,通过这种方式可以寻找转座子
{
int n, min[55] = {'\0'}, max[55] = {'\0'}, cnt = 0, ans = 0;
scanf("%d", &n);//1行的个数
for (int i = 1; i <= n; i ++)
{
min[i] = n;//初始化
}
while(1)
{
for (int i = 1; i <= n; i ++)//从1开始 ,用本地变量,一个循环表示读入一行
{//i记录的是第几个元素
int g;
if(scanf("%d", &g) == EOF)//由于序列个数未知,故通过返回值判断跳出循环
{//g储存元素名称 ,scanf只会读入数字,会跳过空格
break;
}
if(min[g] > i)//min数组记录对应下标的元素的位置 的最小值
{
min[g] = i;
}
if(max[g] < i)//max数组记录对应下标的元素的位置 的最小值
{
max[g] = i;
}
}
}
for(int i = 1; i <= n; i ++)
{
if(max[i] - min[i] > 1)//这里就跳过了第0个元素
{//判断每一个元素的位置变化
cnt ++;//cnt记录转座子数目
ans = i;//ans记录转座子名称
}
}
if(cnt != 1)
{
printf("-1\n");
}
else
{
printf("%d\n", ans);
}
return 0;
}