Максимальная разница между частотой двух элементов, при которой элемент с большей частотой также больше

Опубликовано: 20 Января, 2022

Дан массив из n натуральных чисел с множеством повторяющихся элементов. Задача состоит в том, чтобы найти максимальную разницу между частотами любых двух разных элементов, чтобы элемент с большей частотой также был больше по значению, чем второе целое число.

Примеры:

 Ввод: arr [] = {3, 1, 3, 2, 3, 2}.
Выход: 2
Частота 3 = 3.
Частота 2 = 2.
Частота 1 = 1.
Здесь разница частот элементов 3 и 1 = 3 - 1 = 2.
Также 3> 1.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Метод 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
     

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