Разница между наивысшей и наименьшей частотами в массиве

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

Для данного массива найдите разницу между наибольшим и наименьшим вхождением любого числа в массиве.
Примеры:

 Ввод: arr [] = [7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5]
Выход: 2
Самый низкий элемент (5) встречается один раз.
Самый высокий элемент (1 или 7) встречается 3 раза

Ввод: arr [] = [1, 1, 1, 3, 3, 3]
Выход: 0

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простое решение - использовать две петли для подсчета частоты каждого элемента и отслеживания максимальной и минимальной частот.
Лучшее решение - отсортировать массив за O (n log n) и проверить
последовательных вхождений элементов и сравнить их количество соответственно.

C ++

// CPP code to find the difference between highest
// and least frequencies
#include <bits/stdc++.h>
using namespace std;
int findDiff( int arr[], int n)
{
// sort the array
sort(arr, arr + n);
int count = 0, max_count = 0, min_count = n;
for ( int i = 0; i < (n - 1); i++) {
// checking consecutive elements
if (arr[i] == arr[i + 1]) {
count += 1;
continue ;
}
else {
max_count = max(max_count, count);
min_count = min(min_count, count);
count = 0;
}
}
return (max_count - min_count);
}
// Driver code
int main()
{
int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << findDiff(arr, n) << " " ;
return 0;
}

Джава

// JAVA Code for Difference between
// highest and least frequencies
// in an array
import java.util.*;
class GFG {
static int findDiff( int arr[], int n)
{
// sort the array
Arrays.sort(arr);
int count = 0 , max_count = 0 ,
min_count = n;
for ( int i = 0 ; i < (n - 1 ); i++) {
// checking consecutive elements
if (arr[i] == arr[i + 1 ]) {
count += 1 ;
continue ;
}
else {
max_count = Math.max(max_count,
count);
min_count = Math.min(min_count,
count);
count = 0 ;
}
}
return (max_count - min_count);
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 7 , 8 , 4 , 5 , 4 , 1 ,
1 , 7 , 7 , 2 , 5 };
int n = arr.length;
System.out.println(findDiff(arr, n));
}
}
// This code is contributed by Arnav Kr. Mandal.

Python3

# Python3 code to find the difference
# between highest nd least frequencies
def findDiff(arr, n):
# sort the array
arr.sort()
count = 0 ; max_count = 0 ; min_count = n
for i in range ( 0 , (n - 1 )):
# checking consecutive elements
if arr[i] = = arr[i + 1 ]:
count + = 1
continue
else :
max_count = max (max_count, count)
min_count = min (min_count, count)
count = 0
return max_count - min_count
# Driver Code
arr = [ 7 , 8 , 4 , 5 , 4 , 1 , 1 , 7 , 7 , 2 , 5 ]
n = len (arr)
print (findDiff(arr, n))
# This code is contributed by Shreyanshi Arun.

C #

// C# Code for Difference between
// highest and least frequencies
// in an array
using System;
class GFG {
static int findDiff( int [] arr, int n)
{
// sort the array
Array.Sort(arr);
int count = 0, max_count = 0,
min_count = n;
for ( int i = 0; i < (n - 1); i++) {
// checking consecutive elements
if (arr[i] == arr[i + 1]) {
count += 1;
continue ;
}
else {
max_count = Math.Max(max_count,
count);
min_count = Math.Min(min_count,
count);
count = 0;
}
}
return (max_count - min_count);
}
// Driver program to test above function
public static void Main()
{
int [] arr = { 7, 8, 4, 5, 4, 1,
1, 7, 7, 2, 5 };
int n = arr.Length;
Console.WriteLine(findDiff(arr, n));
}
}
// This code is contributed by vt_m.

PHP

<?php
// PHP code to find the
// difference between highest
// and least frequencies
// function that
// returns difference
function findDiff( $arr , $n )
{
// sort the array
sort( $arr );
$count = 0; $max_count = 0;
$min_count = $n ;
for ( $i = 0; $i < ( $n - 1); $i ++)
{
// checking consecutive elements
if ( $arr [ $i ] == $arr [ $i + 1])
{
$count += 1;
continue ;
}
else
{
$max_count = max( $max_count , $count );
$min_count = min( $min_count , $count );
$count = 0;
}
}
return ( $max_count - $min_count );
}
// Driver Code
$arr = array (7, 8, 4, 5, 4, 1,
1, 7, 7, 2, 5);
$n = sizeof( $arr );
echo (findDiff( $arr , $n ) . " " );
// This code is contributed by Ajit.
?>

Javascript

<script>
// Javascript Code for Difference between
// highest and least frequencies
// in an array
function findDiff(arr, n)
{
// sort the array
arr.sort( function (a, b){ return a - b});
let count = 0, max_count = 0, min_count = n;
for (let i = 0; i < (n - 1); i++) {
// checking consecutive elements
if (arr[i] == arr[i + 1]) {
count += 1;
continue ;
}
else {
max_count = Math.max(max_count, count);
min_count = Math.min(min_count, count);
count = 0;
}
}
return (max_count - min_count);
}
let arr = [ 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 ];
let n = arr.length;
document.write(findDiff(arr, n));
</script>

Выход:

 2

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

C ++

// CPP code to find the difference between highest
// and least frequencies
#include <bits/stdc++.h>
using namespace std;
int findDiff( int arr[], int n)
{
// Put all elements in a hash map
unordered_map< int , int > hm;
for ( int i = 0; i < n; i++)
hm[arr[i]]++;
// Find counts of maximum and minimum
// frequent elements
int max_count = 0, min_count = n;
for ( auto x : hm) {
max_count = max(max_count, x.second);
min_count = min(min_count, x.second);
}
return (max_count - min_count);
}
// Driver
int main()
{
int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << findDiff(arr, n) << " " ;
return 0;
}

Джава

// Java code to find the difference between highest
// and least frequencies
import java.util.*;
class GFG
{
static int findDiff( int arr[], int n)
{
// Put all elements in a hash map
Map<Integer,Integer> mp = new HashMap<>();
for ( int i = 0 ; i < n; i++)
{
if (mp.containsKey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i])+ 1 );
}
else
{
mp.put(arr[i], 1 );
}
}
// Find counts of maximum and minimum
// frequent elements
int max_count = 0 , min_count = n;
for (Map.Entry<Integer,Integer> x : mp.entrySet())
{
max_count = Math.max(max_count, x.getValue());
min_count = Math.min(min_count, x.getValue());
}
return (max_count - min_count);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 7 , 8 , 4 , 5 , 4 , 1 , 1 , 7 , 7 , 2 , 5 };
int n = arr.length;
System.out.println(findDiff(arr, n));
}
}
/* This code is contributed by PrinciRaj1992 */

Python3

# Python code to find the difference between highest
# and least frequencies
from collections import defaultdict
def findDiff(arr,n):
# Put all elements in a hash map
mp = defaultdict( lambda : 0 )
for i in range (n):
mp[arr[i]] + = 1
# Find counts of maximum and minimum
# frequent elements
max_count = 0 ;min_count = n
for key,values in mp.items():
max_count = max (max_count,values)
min_count = min (min_count,values)
return max_count - min_count
# Driver code
arr = [ 7 , 8 , 4 , 5 , 4 , 1 , 1 , 7 , 7 , 2 , 5 ]
n = len (arr)
print (findDiff(arr,n))
# This code is contributed by Shrikant13

C #

// C# code to find the difference between highest
// and least frequencies
using System;
using System.Collections.Generic;
class GFG
{
static int findDiff( int []arr, int n)
{
// Put all elements in a hash map
Dictionary< int , int > mp = new Dictionary< int , int >();
for ( int i = 0 ; i < n; i++)
{
if (mp.ContainsKey(arr[i]))
{
var val = mp[arr[i]];
mp.Remove(arr[i]);
mp.Add(arr[i], val + 1);
}
else
{
mp.Add(arr[i], 1);
}
}
// Find counts of maximum and minimum
// frequent elements
int max_count = 0, min_count = n;
foreach > entry (KeyValuePair< int , int in mp)
{
max_count = Math.Max(max_count, entry.Value);
min_count = Math.Min(min_count, entry.Value);
}
return (max_count - min_count);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
int n = arr.Length;
Console.WriteLine(findDiff(arr, n));
}
}
// This code is contributed by Princi Singh

Выход:

 2

Сложность времени: O (n)
Эта статья предоставлена Химаншу Ранджан . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Разница между

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

В чем разница между спринтом, итерацией и инкрементом?
22 Февраля, 2023
C++ STL против платформы коллекций Java
19 Февраля, 2023
Разница между азотом и фосфором
10 Февраля, 2023
Различие между каналом затопления и многолетним каналом
9 Февраля, 2023
Различие между коттеджным и малым производством
9 Февраля, 2023
Kuberneters — разница между набором реплик и контроллером репликации
28 Января, 2023
Android — разница между RecyclerView и ListView
28 Января, 2023
Разница между NAND GATE и NOR GATE
28 Января, 2023