10609. Первый элемент встречающийся k раз в массиве

 

Задан массив n целых чисел. Найдите первый элемент, который встречается k раз. Если никакой элемент не встречается k раз, то выведите -1.

 

Вход. Первая строка содержит два натуральных числа n и k (n, k ≤ 105). Вторая строка содержит n целых чисел, каждое по модулю не больше 109.

 

Выход. Выведите первый элемент, который встречается k раз. Если никакой элемент не встречается k раз, то выведите -1.

 

Пример входа 1

Пример выхода 1

7 2

1 7 4 3 4 8 7

7

 

 

Пример входа 2

Пример выхода 2

6 1

4 1 6 1 6 4

-1

 

 

РЕШЕНИЕ

структуры данных map

 

Анализ алгоритма

Для каждого числа x из последовательности подсчитаем в структуре данных map количество раз m[x], которое оно встречается в последовательности. Далее найдем первый элемент последовательности, для которого m[x] = k (который встречается k раз).

 

Реализация алгоритма

Объявим структуры данных.

 

map<int, int> m;

vector<int> v;

 

Основная часть программы. Входную последовательность читаем в массив v. Для каждого числа x в m[x] подсчитываем количество раз, которое оно встречается в последовательности.

 

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

  v.push_back(x);

  m[x]++;

}

 

Перебираем элементы последовательности. Как только будет найдено v[i], которое встречается k раз, выводим его и завершаем программу.

 

for (i = 0; i < n; i++)

  if (m[v[i]] == k)

  {

    printf("%d\n", v[i]);

    return 0;

  }

 

Искомое значение не найдено. Выводим -1.

 

printf("-1\n");

 

Java реализация

 

import java.util.*;

 

public class Main

{

  static Map<Integer, Integer> m = new HashMap<Integer, Integer>();

  static ArrayList<Integer> a = new ArrayList<Integer>();

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int k = con.nextInt();

 

    for (int i = 0; i < n; i++)

    {

      int x = con.nextInt();

      a.add(x);

      int val = (m.containsKey(x)) ? m.get(x) : 0;

      m.put(x, val + 1);

    }

   

    for (int i = 0; i < n; i++)

      if (m.get(a.get(i)) == k)

      {

        System.out.println(a.get(i));

        con.close();

        return;

      }

   

    System.out.println(-1);

    con.close();

  }

}