个性化阅读
专注于IT技术分析

算法:数组元素最高和最低频率之间的差异

本文概述

给定一个数组, 找出数组中任何数字出现次数最多和最少的差异

例子:

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 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)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

赞(0) 打赏
未经允许不得转载:srcmini » 算法:数组元素最高和最低频率之间的差异
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏