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

本文概述

  • 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)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

    推荐阅读