srcmini本文概述
给定一个数组, 找出数组中任何数字出现次数最多和最少的差异
例子：
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 times
Input : 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 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 ) . "\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 Shrikant13C#
//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)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
评论前必须登录！
注册