本文概述
- C ++
- Java
- Python3
- C#
- 的PHP
- C ++
- Java
- Python3
- C#
例子:
Input: arr[] = [7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5]
Output : 2
Lowest occurring element (5) occurs once.
Highest occurring element (1 or 7) occurs 3 timesInput: arr[] = [1, 1, 1, 3, 3, 3]
Output : 0
一种简单的解决方案是使用两个循环来计数每个元素的频率, 并跟踪最大和最小频率。
一种更好的解决方案是将数组排序并检查: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) <
<
"\n" ;
return 0;
}
Java
//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 frequenciesdef 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 ) . "\n" );
//This code is contributed by Ajit.
?>
输出如下:
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) <
<
"\n" ;
return 0;
}
Java
//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 (KeyValuePair<
int , int>
entry 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)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- Hive和HBase之间有什么区别()
- 微服务架构 | 5. 服务容灾
- Linux内核内存管理总结
- sed -n 和 -i 不要一起用
- [首发][Ubuntu]VSCode搭建Linux Kernel单步调试IDE环境
- 视频更新(代码分析8之单步调试ARM64启动汇编与重定位)
- 灵魂拷问之调度与切换十六问
- (系统级I?O)
- 运维小白成长记——第六周