Calcul du mode statistique

Question

J'essaie actuellement de vérifier si, compte tenu d'un tableau non trié A de longueur N et d'un entier k, il existe ou non un élément qui apparaît n/k fois ou plus. Je pensais à ce problème en calculant le mode, puis en le comparant à n/k. Cependant, je ne sais pas comment calculer ce mode rapidement. Mon résultat final doit être n log (k), mais je ne sais pas vraiment comment faire cela. Le plus rapide que je pouvais trouver était n k ...

Answer 1

Utilisez une table de hachage pour compter la fréquence de chaque valeur:

uint[int] counts; 
foreach(num; myArray) { 
    counts[num]++; 
} 

int mostFrequent; 
uint maxCount = 0; 
foreach(num, count; counts) { 
    if(count > maxCount) { 
     mostFrequent = num; 
     maxCount = count; 
    } 
} 

Answer 2

Il suffit de marcher le tableau et garder compte dans un hachage/dictionnaire (et retour vrai une fois n/k est trouvé, sinon faux) serait O (n)

modifier, quelque chose comme:

counts = {} 
for n in numbers: 
    if (counts.has_key(n)): 
     counts[ n ] += 1 
    else: 
     counts[ n ] = 1 
    if (counts[ n ] >= n/k): 
     return true 
return false 

Answer 3

pseudocode:

found = false 
value = null 
B = new hashtable 
for (i =0, j = A[i]; i < |A| and !found; ++i, j=A[i]) 
    if B contains key j 
     B[j] = B[j] + 1 
     if B[j] > |A|/k 
      found = true 
      value = j 
     endif 
    else 
     B[j] = 1 
    endif 
end for 

En supposant que votre mise en œuvre Hashtable a O (1) insérer/recherche ce doit être O (n)

Answer 4

Set m = n/k arrondi. Faites un quicksort, mais rejetez les sous-listes de longueur inférieure à m. Comme le quicksort, vous pouvez avoir de la malchance et choisir à plusieurs reprises des pivots proches des extrémités. Mais cela a une petite probabilité de se produire, si vous choisissez les pivots au hasard.

Il y aura des niveaux O (log (k)) pour la récursion, et chaque niveau prend le temps O (n).

Answer 5

Calcul du mode statistique en F # .net pour jeu de données (entiers) qui a monomodes

let foundX (num: int, dList) = List.filter (fun x -> x = num) dList 
let groupNum dList = 
    dList 
    |> (List.map (fun x -> foundX (x, dList))) 
    |> (List.maxBy (fun x -> x.Length)) 

let Mode (dList: int List) = 
    let x = groupNum dList 
    x.Head 

//using Mode 
let data = [1;1;1;1;1;1;1;1;2;2;3;3;3;1;4;4;4;4;4] 
Mode data;;`