杭电OJ BestCoder28期1001Missing number问题（小技巧偏移法）

1.先描述一下问题：

小yb有一个排列，但他不小心弄丢了其中的两个数字。现在他告诉你他现在手上还有哪些数字，需要你告诉他他丢了哪两个数字。

输入描述

有多组数据，第一行为数据组数T(T≤10)。

对于每组数据，第一行为一个正整数n，表示yb现在手上有的数字个数。

在接下来一行有n个整数，保证所有数字互不相同且合法。

1≤n≤1,000

输出描述

对于每组数据，输出两个数字，为排列缺少的两个数字，小的在前。

2.解题思路

该问题可以用一个数组存储输入排列,然后用一个偏移指针处理每次输入数据移动的情况。（为了处理出现 1 3 这种序列的情况，需要在输入数据的末尾加入一个0）
具体的移动情况如下图所示：

3.代码如下

　　#include <stdio.h>
　　#include <stdlib.h>

　　#define MAX_NUM 1000 + 10

　　int main()
　　{
　　　　int i,j,num_case,num_number,number[MAX_NUM];

　　　　int offset = 0,count = 0; //偏移

　　　　scanf("%d",&num_case);

　　　　for( i = 1; i <= num_case; i++)
　　　　{
　　　　　　offset = 0;
　　　　　　count = 0;
　　　　　　scanf("%d",&num_number);
　　　　　　for( j = 0; j < num_number; j++)
　　　　　　{
　　　　　　　　scanf("%d",&number[j]);
　　　　　　}

　　　　　　number[j] = 0; //处理当出现 1 3 这种排列的状况而使offset偏移溢出

　　　　　　for( j = 0; j < num_number + 2; j++)
　　　　　　{
　　　　　　　　if(count >= 2)
　　　　　　　　{
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　if( number[offset] == j + 1 )
　　　　　　　　{
　　　　　　　　　　offset++;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　printf("%d ",j + 1);
　　　　　　　　　　count++;
　　　　　　　　}
　　　　　　}
　　　　　　printf("\n");
　　　　}
　　}

巴特西

杭电OJ BestCoder28期1001Missing number问题（小技巧偏移法）

最新文章

热门文章