Максимальная разница между частотой двух элементов, при которой элемент с большей частотой также больше
Дан массив из n натуральных чисел с множеством повторяющихся элементов. Задача состоит в том, чтобы найти максимальную разницу между частотами любых двух разных элементов, чтобы элемент с большей частотой также был больше по значению, чем второе целое число.
Примеры:
Ввод: arr [] = {3, 1, 3, 2, 3, 2}. Выход: 2 Частота 3 = 3. Частота 2 = 2. Частота 1 = 1. Здесь разница частот элементов 3 и 1 = 3 - 1 = 2. Также 3> 1.
Метод 1 (использовать хеширование):
Наивный подход может заключаться в том, чтобы найти частоту каждого элемента и для каждого элемента найти элемент, имеющий меньшее значение и меньшую частоту, чем текущий элемент.
Below is the implementation of this approach:
C++
// C++ program to find maximum difference // between frequency of any two element // such that element with greater frequency // is also greater in value. #include<bits/stdc++.h> using namespace std; // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. int maxdiff( int arr[], int n) { unordered_map< int , int > freq; // Finding the frequency of each element. for ( int i = 0; i < n; i++) freq[arr[i]]++; int ans = 0; for ( int i=0; i<n; i++) { for ( int j=0; j<n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq[arr[i]] > freq[arr[j]] && arr[i] > arr[j] ) ans = max(ans, freq[arr[i]]-freq[arr[j]]); else if (freq[arr[i]] < freq[arr[j]] && arr[i] < arr[j] ) ans = max(ans, freq[arr[j]]-freq[arr[i]]); } } return ans; } // Driven Program int main() { int arr[] = { 3, 1, 3, 2, 3, 2 }; int n = sizeof (arr)/ sizeof (arr[0]); cout << maxdiff(arr, n) << endl; return 0; } |
Java
// Java program to find maximum difference // between frequency of any two element // such that element with greater frequency // is also greater in value. import java.util.*; class GFG { // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. static int maxdiff( int arr[], int n) { Map<Integer, Integer> freq = new HashMap<>(); // Finding the frequency of each element. for ( int i = 0 ; i < n; i++) freq.put(arr[i], freq.get(arr[i]) == null ? 1 : freq.get(arr[i]) + 1 ); int ans = 0 ; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq.get(arr[i]) > freq.get(arr[j]) && arr[i] > arr[j]) ans = Math.max(ans, freq.get(arr[i]) - freq.get(arr[j])); else if (freq.get(arr[i]) < freq.get(arr[j]) && arr[i] < arr[j] ) ans = Math.max(ans, freq.get(arr[j]) - freq.get(arr[i])); } } return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 1 , 3 , 2 , 3 , 2 }; int n = arr.length; System.out.println(maxdiff(arr, n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python program to find maximum difference # between frequency of any two element # such that element with greater frequency # is also greater in value. from collections import defaultdict # Return the maximum difference between # frequencies of any two elements such that # element with greater frequency is also # greater in value. def maxdiff(arr, n): freq = defaultdict( lambda : 0 ) # Finding the frequency of each element. for i in range (n): freq[arr[i]] + = 1 ans = 0 for i in range (n): for j in range (n): # finding difference such that element # having greater frequency is also # greater in value. if freq[arr[i]] > freq[arr[j]] and arr[i] > arr[j]: ans = max (ans, freq[arr[i]] - freq[arr[j]]) elif freq[arr[i]] < freq[arr[j]] and arr[i] < arr[j]: ans = max (ans, freq[arr[j]] - freq[arr[i]]) return ans arr = [ 3 , 1 , 3 , 2 , 3 , 2 ] n = len (arr) print (maxdiff(arr,n)) # This code is contributed by Shrikant13 |
C#
// C# program to find maximum difference // between frequency of any two element // such that element with greater frequency // is also greater in value. using System; using System.Collections.Generic; class GFG { // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. static int maxdiff( int [] arr, int n) { Dictionary< int , int > freq = new Dictionary< int , int >(); // Finding the frequency of each element. for ( int i = 0; i < n; i++) { if (freq.ContainsKey(arr[i])) freq[arr[i]]++; else freq.Add(arr[i], 1); } int ans = 0; for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq[arr[i]] > freq[arr[j]] && arr[i] > arr[j]) ans = Math.Max(ans, freq[arr[i]] - freq[arr[i]]); else if (freq[arr[i]] < freq[arr[j]] && arr[i] < arr[j]) ans = Math.Max(ans, freq[arr[j]] - freq[arr[i]]); } } return ans; } // Driver Code public static void Main(String[] args) { int [] arr = { 3, 1, 3, 2, 3, 2 }; int n = arr.Length; Console.WriteLine(maxdiff(arr, n)); } } // This code is contributed by // sanjeev2552 |
Javascript
<script> // JavaScript program to find maximum difference // between frequency of any two element // such that element with greater frequency // is also greater in value. // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. function maxdiff(arr, n) { let freq = new Map(); // Finding the frequency of each element. for (let i = 0; i < n; i++) freq.set(arr[i], freq.get(arr[i]) == null ? 1 : freq.get(arr[i]) + 1); let ans = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq.get(arr[i]) > freq.get(arr[j]) && arr[i] > arr[j]) ans = Math.max(ans, freq.get(arr[i]) - freq.get(arr[j])); else if (freq.get(arr[i]) < freq.get(arr[j]) && arr[i] < arr[j] ) ans = Math.max(ans, freq.get(arr[j]) - freq.get(arr[i])); } } return ans; } // Driver code let arr = [ 3, 1, 3, 2, 3, 2 ]; let n = arr.length; document.write(maxdiff(arr, n)); </script> |
Выход:
2
Сложность времени: O (n 2 ).
Метод 2 (использовать хеширование и сортировку):
Идея состоит в том, чтобы найти все отдельные элементы и сохранить их в массиве, скажем, dist []. Отсортируйте массив отдельных элементов dist [] в порядке возрастания. Теперь для любого отдельного элемента с индексом i, для всего индекса j, такого что i> j> 0, найдите элемент от индекса 0 до i-1, имеющий минимальную частоту. Мы можем найти частоту элемента так же, как метод 1, то есть сохраняя частоты в хеш-таблице.
Сделайте это для всех i и найдите максимальную разницу. Чтобы найти минимальную частоту для всех, я поддерживаю минимум префикса.
Below is representation of this approach:
C++
// Efficient C++ program to find maximum // difference between frequency of any two // elements such that element with greater // frequency is also greater in value. #include<bits/stdc++.h> using namespace std; // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. int maxdiff( int arr[], int n) { unordered_map< int , int > freq; int dist[n]; // Finding the frequency of each element. int j = 0; for ( int i = 0; i < n; i++) { if (freq.find(arr[i]) == freq.end()) dist[j++] = arr[i]; freq[arr[i]]++; } // Sorting the distinct element sort(dist, dist + j); int min_freq = n+1; // Iterate through all sorted distinct elements. // For each distinct element, maintaining the // element with minimum frequency than that // element and also finding the maximum // frequency difference int ans = 0; for ( int i=0; i<j; i++) { int cur_freq = freq[dist[i]]; ans = max(ans, cur_freq - min_freq); min_freq = min(min_freq, cur_freq); } return ans; } // Driven Program int main() { int arr[] = { 3, 1, 3, 2, 3, 2 }; int n = sizeof (arr)/ sizeof (arr[0]); cout << maxdiff(arr, n) << endl; return 0; } |
Java
// Efficient Java program to find maximum // difference between frequency of any two // elements such that element with greater // frequency is also greater in value. import java.util.*; class GFG { // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. static int maxdiff( int arr[], int n) { HashMap<Integer,Integer> freq= new HashMap<>(); int []dist = new int [n]; // Finding the frequency of each element. int j = 0 ; for ( int i = 0 ; i < n; i++) { dist[j++] = arr[i]; if (!freq.containsKey(arr[i])) freq.put(arr[i], 1 ); else freq.put(arr[i], freq.get(arr[i]) + 1 ); } // Sorting the distinct element Arrays.sort(dist); int min_freq = n + 1 ; // Iterate through all sorted distinct elements. // For each distinct element, maintaining the // element with minimum frequency than that // element and also finding the maximum // frequency difference int ans = 0 ; for ( int i = 0 ; i < j; i++) { int cur_freq = freq.get(dist[i]); ans = Math.max(ans, cur_freq - min_freq); min_freq = Math.min(min_freq, cur_freq); } return ans; } // Driven Program public static void main(String[] args) { int arr[] = { 3 , 1 , 3 , 2 , 3 , 2 }; int n = arr.length; System.out.print(maxdiff(arr, n) + "
" ); } } // This code is contributed by Rajput-Ji |
Python3
# Efficient Python3 program to find maximum # difference between frequency of any two # elements such that element with greater # frequency is also greater in value. # Return the maximum difference between # frequencies of any two elements such that # element with greater frequency is also # greater in value. def maxdiff(arr, n): freq = {} dist = [ 0 ] * n
РЕКОМЕНДУЕМЫЕ СТАТЬИ |