Найти заданные вхождения M-го наиболее частого элемента массива

Опубликовано: 19 Сентября, 2022

Учитывая массив arr[] , целое число M и массив query[] , содержащий Q запросов, задача состоит в том, чтобы найти query[i] -е вхождение M -го наиболее часто встречающегося элемента массива.

Примеры:

Input: arr[] = {1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2},  M = 1, query[] = {100, 4, 2}
Output: -1, 12, 5
Explanation: Here most frequent Integer = 8, with frequency = 4
Thus for Query
1) For k = 100, Output-> -1 (100th element not available)
2) For k = 4, Output -> 12 (4th occurrence of 8 is at 12th index)
3) For k = 2, Output -> 5 (2nd occurrence of 8 is at 5th index)

Input: arr[] = {2, 2, 20, 8, 8, 1, 2, 5}, M = 2, query[] = {2, 3}
Output: 4, -1

Подход: Решение задачи основано на следующей идее:

Find the Mth most frequent element. Then store all the occurrences of the integers and find the query[i]th occurrence of the Mth most frequent element.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Объявите карту для целого числа и вектора.
  • Пройдите через входной массив и сохраните уникальные элементы на карте как ключи.
    • Затем вставьте индекс вхождений этого элемента в вектор.
  • Сохраните уникальные элементы с их частотой и найдите M-й наиболее часто встречающийся элемент.
  • Снова пройдитесь по запросам.
    • Для каждого запроса проверьте, если K <размер вектора, затем верните -1 .
    • В противном случае сохраните индексы в элемент.

Следуйте приведенной ниже иллюстрации для лучшего понимания

Иллюстрация:

arr[] = {1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2}, M = 1
Query_val = {100, 4, 2}

Now for Each element the frequency and occurred indexes are:

1  -> 1, 6           frequency : 2
2  -> 2, 7, 13     frequency : 3
20 -> 3              frequency : 1
8  -> 4, 5, 9, 12  frequency : 4
5  -> 8               frequency : 1
0  -> 10             frequency : 1
6  -> 11             frequency : 1

Thus maximum frequency element = 8 with frequency 4

Now for queries
For k = 100, -> -1  (k > maxfre)
For K = 4,   -> 12  ((K-1) index of vector) 
For K = 2,   -> 5   ((K-1) index of vector)   

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N + Q + K * logK) Q = количество запросов, K = количество уникальных элементов.
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ