Найти заданные вхождения M-го наиболее частого элемента массива
Учитывая массив 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 : 1Thus 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)