Задана
последовательность из n натуральных чисел. Определите, является ли она
перестановкой первых n натуральных чисел.
Вход. В одной строке сначала дано число n (n
≤ 10000), а затем следует последовательность из n натуральных
чисел. Известно, что каждое из этих чисел не превышает 2 * 106.
Выход. Выведите 0,
если последовательность является перестановкой. Иначе выведите наименьшее
число, отсутствующее в этой последовательности.
|
Пример
входа |
Пример
выхода |
|
3 1 4 2 |
3 |
сортировка подсчетом
Объявим линейный
массив m длины n ≤ 10000. В ячейку m[i] занесем количество
чисел i во входной последовательности. Если все значения m[1], m[2], …,
m[n] будут ненулевыми (во входной последовательности ровно n чисел),
то все они равны 1, и на входе содержится перестановка. В противном случае
выводим наименьшее i, для которого m[i] = 0.
Если какое-либо
число во входной последовательности больше n, то такая
последовательность не является перестановкой.
Количество
входных натуральных чисел n не превышает 10000. Объявим линейный массив.
#define MAX 10002
int m[MAX];
Читаем входные
данные. Обнуляем массив m.
scanf("%d",&n);
memset(m,0,sizeof(m));
Для каждого
входного числа а ≤ n увеличим m[a] на единицу (при
этом а может принимать значение от 1 до 2 * 106).
for (i = 0; i < n; i++)
{
scanf("%d",&a);
if (a <=
n) m[a]++;
}
Находим
наименьшее натуральное число i, которого нет во входной последовательности.
Для такого числа будет выполнено условие m[i] = 0.
for (i = 1; i <= n; i++)
if (m[i] ==
0) break;
Если i > n, это означает, что все числа от 1 до n присутствуют, и входная
последовательность является перестановкой. В противном случае i будет наименьшим числом,
отсутствующим в этой последовательности.
if (i <= n) printf("%d\n",i); else
printf("0\n");
Java реализация
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int i, n = con.nextInt();
int m[] = new int[n+1];
for(i = 0; i < n; i++)
{
int a = con.nextInt();
if (a <= n) m[a]++;
}
for(i = 1; i <= n; i++)
if (m[i] == 0) break;
if (i <= n)
System.out.println(i);
else
System.out.println(0);
con.close();
}
}