Recherche d'un nombre entier maximal (mode) dans un tableau non trié

Question

Comment trouver l'entier survenant le nombre maximal de fois (mode) dans un tableau non trié d'entiers? Une approche O(nlogn) Je pourrais penser à trier. Y a-t-il une autre meilleure approche?

Answer 1

Je pense que vous voulez savoir l'élément qui a le plus occurences dans le tableau - si vous ne se soucient pas de la mémoire, traverse le tableau une fois , augmente le nombre de chaque élément dans la table de hachage. Ensuite, trouvez celui qui compte le plus. Vous auriez besoin d'une traverse de tableau et une de la table de hachage.

donc en pseudocode:

hashtable hash; 
foreach(element in array){ 
    if(!hash.contains(element)) 
    hash[element] = 1; 
    else 
    hash[element]++; 
} 

int max = 0; 
max_element; 
foreach(element in hash) 
    if(hash[element] > max) 
    { 
    max_element = element; 
    max = hash[element]; 
    } 

//max_element contains the maximum occuring one. 

Answer 2

Si vous utilisez LINQ, vous pouvez le faire

IEnumerable.Max(); 

Answer 3

Vous pouvez utiliser une table de hachage avec « le nombre dans le tableau » comme clé et « événements » comme valeurs.

Exemple de code comme ceci:

hashtable h; 
for every entry in array 
     search hashtable 
      if present, increment num_occurrences 
      else, create new entry 

Iterate over all the entries in hashtable and return one 
with max num_occurrences 

Comme la recherche dans hash est considéré comme O (1), la complexité globale sera O (n). Un cas particulier de ce problème est lorsque les nombres dans le tableau sont dans une plage donnée, dans ce cas, prenez un autre tableau d'ints avec la taille de la valeur maximale dans le tableau original, et utilisez l'index du nouveau tableau comme clé et le nombre stocké dans ce tableau en tant que nombre d'occurrences.

Renvoie l'indice de la plus grande valeur de ce tableau.

Answer 4

Voici un aperçu de base de ce que vous allez faire:

1. d'abord trier le tableau - O (n log n) Encas d'un tri par fusion
2. Declare Count = 1, MAX_COUNT = 1, MAX_VALUE = arr [0]
3. Itérer au sein d'un tableau à partir de l'index 1
4. Comparer chaque élément avec l'élément précédent. Mettre à jour le compte, MAX_COUNT si elles sont égales, sinon remis à zéro compte revenir à 1
5. retour MAX_COUNT, MAX_VALUE

 
Time Complexity : O(n logn)+ O(n) 
Space Complexity : InPlace , no hash table or hash map is required. 

Voici le code:

public void Max_Occurrence(int[] arr) 
{ 
    int count=1; 
    int max_count =1; 
    int max_value = arr[0]; 
    for(int i=1; i<arr.length ; i++) 
    { 
     if(arr[i-1] == arr[i]) 
     { 
      count++; 
      if(max_count<count) 
      { 
       max_count = count; 
       max_value = arr[i]; 
      } 
     } 
     else 
     { 
      count = 1;//changing from count++. As per the steps mentioned above it should be reset to count = 1. Suggested by an anonymous user 
     } 
    } 

    System.out.println("Result:"+max_value+" has occured "+max_count+"of times"); 
} 

Answer 5

essayer.

class max_frequency 
{ 
private int a[]=new int[20]; 
public void accept(int a1[]) 
{ 
    a=a1; 
} 
public void sort() 
{ 
    int i,j,t; 
    for(i=0;i<20;i++) 
    { 
     for(j=i+1;j<20;j++) 
     { 
      if(a[i]>a[j]) 
      { 
       t=a[i]; 
       a[i]=a[j]; 
       a[j]=t; 
      } 
     } 
    } 
    int count=1; 
    int max_count=1; 
    int max_value=0; 
    for(i=1;i<a.length;i++) 
    { 
     if(a[i-1]==a[i]) 
     { 
      count++; 
      if(max_count<count) 
      { 
       max_count=count; 
       max_value=a[i]; 
      } 
     } 
     else 
     { 
      count=1; 
     } 
    } 
     System.out.println("Result : "+max_value+ " has occured "+max_count+ " times"); 
} 

}