Самый частый элемент в массиве после замены данного индекса на K для Q запросов
Дан массив arr [] размера N и Q запросов формы {i, k}, для которых задача состоит в том, чтобы напечатать наиболее часто встречающийся элемент в массиве после замены arr [i] на k .
Пример :
Input: arr[] = {2, 2, 2, 3, 3}, Querry = {{0, 3}, {4, 2}, {0, 4}}
Output: 3 2 2
First query: Setting arr[0] = 3 modifies arr[] = {3, 2, 2, 3, 3}. So, 3 has max frequency.
Second query: Setting arr[4] = 2, modifies arr[] = {3, 2, 2, 3, 2}. So, 2 has max frequency.
Third query: Setting arr[0] = 4, modifies arr[] = {4, 2, 2, 3, 2}. So, 2 has max frequency
Input: arr[] = {1, 2, 3, 4, 3, 3} Querry = {{0, 2}, {3, 2}, {2, 4}}
Output: 3 2 2
Наивный подход:
Для каждого запроса замените arr [i] на K, пройдитесь по всему массиву, посчитайте частоту каждого элемента массива и выведите наиболее частый из них.
Сложность времени: O (N * Q)
Вспомогательное пространство: O (N)
Эффективный подход:
Вышеупомянутый подход можно оптимизировать, предварительно вычислив частоты каждого элемента массива и поддерживая пары частота-элемент массива в наборе, чтобы получить наиболее часто встречающийся элемент в O (1). Выполните следующие действия, чтобы решить проблему:
- Инициализируйте карту для хранения частот всех элементов массива, а набор пар-элементов хранит пары "частота-элемент". В наборе сохраните частоты как отрицательные. Это гарантирует, что первая пара, хранящаяся в начале набора, iesbegin (), является парой {- (максимальная частота), наиболее частый элемент} .
- Для каждого запроса, удаляя элемент массива по i- му индексу, выполните следующие задачи:
- Найдите частоту arr [i] по карте, то есть mp [arr [i]].
- Удалите из набора пару {-mp [arr [i]], arr [i]} .
- Обновите набор после уменьшения частоты arr [i] , вставив {- (mp [arr [i] - 1), arr [i]} в набор.
- Уменьшите частоту arr [i] на карте.
- Чтобы вставить K в массив для каждого запроса, сделайте следующее:
- Найдите частоту K по карте, то есть mp [K] .
- Удалите из множества пару {-mp [K], K}.
- Обновите набор после увеличения частоты K , вставив в набор {- (mp [K] + 1), K} .
- Увеличьте частоту K на карте.
- Наконец, для каждого запроса извлеките пару в начале набора. Первый элемент в наборе обозначает - (максимальная частота) . Следовательно, второй элемент будет наиболее частым элементом. Выведите второй элемент пары.
Ниже представлена реализация описанного выше подхода:
C ++
// C++ program to find the most // frequent element after every // update query on the array #include <bits/stdc++.h> using namespace std; typedef long long int ll; // Function to print the most // frequent element of array // along with update querry void mostFrequent(ll arr[], ll n, ll m, vector<vector<ll> > q) { ll i; // Stores element->fequencies // mappings map<ll, ll> mp; for (i = 0; i < n; i++) mp[arr[i]] += 1; // Stores frequencies->element // mappings set<pair<ll, ll> > s; // Store the frequencies in // negative for ( auto it : mp) { s.insert(make_pair(-(it.second), it.first)); } for (i = 0; i < m; i++) { // Index to be modified ll j = q[i][0]; // Value to be inserted ll k = q[i][1]; // Store the frequency of // arr[j] and k auto it = mp.find(arr[j]); auto it2 = mp.find(k); // Remove mapping of arr[j] // with previous frequency s.erase(make_pair(-(it->second), it->first)); // Update mapping with new // frequency s.insert(make_pair(-((it->second) - 1), it->first)); // Update frequency of arr[j] // in the map mp[arr[j]]--; // Remove mapping of k // with previous frequency s.erase(make_pair(-(it2->second), it2->first)); // Update mapping of k // with previous frequency s.insert(make_pair(-((it2->second) + 1), it2->first)); // Update frequency of k mp[k]++; // Replace arr[j] by k arr[j] = k; // Display maximum frequent element cout << (*s.begin()).second << " " ; } } // Driver Code int main() { ll i, N, Q; N = 5; Q = 3; ll arr[] = { 2, 2, 2, 3, 3 }; vector<vector<ll> > querry = { { 0, 3 }, { 4, 2 }, { 0, 4 } }; mostFrequent(arr, N, Q, querry); } |
Джава
// Java program to find the most // frequent element after every // update query on the array import java.util.*; import java.io.*; class GFG{ // Pair class represents // a pair of elements static class Pair { int first, second; Pair( int f, int s) { first = f; second = s; } } // Function to print the most // frequent element of array // along with update querry static void mostFrequent( int arr[], int n, int m, ArrayList<Pair> q) { int i; // Stores element->fequencies // mappings HashMap<Integer, Integer> map = new HashMap<>(); HashMap<Integer, Pair> map1 = new HashMap<>(); for (i = 0 ; i < n; i++) { if (!map.containsKey(arr[i])) map.put(arr[i], 1 ); else map.put(arr[i], map.get(arr[i]) + 1 ); } // Stores frequencies->element // mappings TreeSet<Pair> set = new TreeSet<>( new Comparator<Pair>() { public int compare(Pair p1, Pair p2) { return p2.first - p1.first; } }); // Store the frequencies in // bigger to smaller for (Map.Entry<Integer, Integer> entry : map.entrySet()) { Pair p = new Pair(entry.getValue(), entry.getKey()); set.add(p); map1.put(entry.getKey(), p); } for (i = 0 ; i < m; i++) { // Index to be modified int j = q.get(i).first; // Value to be inserted int k = q.get(i).second; // Insert the new Pair // with value k if it was // not inserted if (map1.get(k) == null ) { Pair p = new Pair( 0 , k); map1.put(k, p); set.add(p); } // Get the Pairs of // arr[j] and k Pair p1 = map1.get(arr[j]); set.remove(p1); Pair p2 = map1.get(k); set.remove(p2); // Decrease the frequency of // mapping with value arr[j] p1.first--; set.add(p1); // Update frequency of arr[j] // in the map map.put(arr[j], map.get(arr[j]) - 1 ); // Increase the frequency of // mapping with value k p2.first++; set.add(p2); // Update frequency of k if (map.containsKey(k)) map.put(k, map.get(k) + 1 ); else map.put(k, 1 ); // Replace arr[j] by k arr[j] = k; // Display maximum frequent element System.out.print( set.iterator().next().second + " " ); } } // Driver Code public static void main(String []args) { int i, N, Q; N = 5 ; Q = 3 ; int arr[] = { 2 , 2 , 2 , 3 , 3 }; ArrayList<Pair> query = new ArrayList<>(); query.add( new Pair( 0 , 3 )); query.add( new Pair( 4 , 2 )); query.add( new Pair( 0 , 4 )); mostFrequent(arr, N, Q, query); } } // This code is contributed by Ganeshchowdharysadanala |
Python3
# Python program to find the most # frequent element after every # update query on the array from typing List import from collections import defaultdict # Function to print the most # frequent element of array # along with update querry def mostFrequent(arr: List [ int ], n: int , m: int , q: List [ List [ int ]]) - > None : i = 0 # Stores element->fequencies # mappings mp = defaultdict( lambda : 0 ) for i in range (n): mp[arr[i]] + = 1 # Stores frequencies->element # mappings s = set () # Store the frequencies in # negative for k, v in mp.items(): s.add(( - v, k)) for i in range (m): # Index to be modified j = q[i][ 0 ] # Value to be inserted k = q[i][ 1 ] # Store the frequency of # arr[j] and k it = mp[arr[j]] it2 = mp[k] # Remove mapping of arr[j] # with previous frequency if ( - it, arr[j]) in s: s.remove(( - it, arr[j])) # Update mapping with new # frequency s.add(( - (it - 1 ), arr[j])) # Update frequency of arr[j] # in the map mp[arr[j]] - = 1 # Remove mapping of k # with previous frequency if ( - it2, k) in s: s.remove(( - it2, k)) # Update mapping of k # with previous frequency s.add(( - (it2 + 1 ), k)) # Update frequency of k mp[k] + = 1 # Replace arr[j] by k arr[j] = k # Display maximum frequent element print ( sorted (s)[ 0 ][ 1 ]) # Driver Code if __name__ = = "__main__" : N = 5 Q = 3 arr = [ 2 , 2 , 2 , 3 , 3 ] querry = [[ 0 , 3 ], [ 4 , 2 ], [ 0 , 4 ]] mostFrequent(arr, N, Q, querry) # This code is contributed by sanjeev2552 |
Выход:
3 2 2
Сложность времени: O (N + (Q * LogN))
Вспомогательное пространство: O (N)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.