Berechnen des statistischen Modus

Question

Ich versuche zur Zeit, um zu überprüfen, ob oder nicht, eine unsortierte Array A der Länge N gegeben und eine ganze Zahl k, ob es ein Element vorhanden ist, das n / k-fache oder mehr.

tritt auf

Mein Denken für dieses Problem war, um den Modus zu berechnen und dann diese vergleichen zu n / k. Allerdings weiß ich nicht, wie Sie diesen Modus schnell zu berechnen. Mein Endergebnis muss n log (k) sein, aber ich habe keine Ahnung, wirklich, wie dies zu tun. Die schnellst ich finden konnte, war n k ...

Answer 1

Verwenden einer Hash-Tabelle, um die Frequenz jeder Wert zu zählen:

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

Set m = n / k aufzurunden. Führen Sie eine quicksort, aber verwerfen Sublisten einer Länge von weniger als m.

Wie quicksort können Sie Pech haben und immer wieder schwenkt wählen, die an den Enden schließen. Das hat aber eine geringe Wahrscheinlichkeit geschieht, wenn Sie die Zapfen zufällig wählen.

Es wird sein O (log (k)) Ebenen der Rekursion, und jede Ebene nimmt O (n) Zeit.

Answer 3

Sie einfach das Array zu Fuß und halte Zählungen in einem Hash / Wörterbuch (und Rückkehr einmal wahr n / k gefunden wird, sonst false) würde O (n) sein

bearbeiten, so etwas wie:

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 4

Berechnung der statistischen Modus in F # .net für Datensatz (Integer), die Single-Mode hat

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;;`

Answer 5

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

Unter der Annahme, dass Ihre hashtable Implementierung hat O (1) einfügen / Nachschlag sollte O (n) sein