Calculando o modo estatístico

Question

Estou actualmente a tentar verificar se ou não, tendo em conta uma matriz não triados A de comprimento N e um número inteiro k, se existir algum elemento que ocorre n / k vezes ou mais.

O meu pensamento para este problema era para calcular o modo e, em seguida, comparar isso com n / k. No entanto, eu não sei como calcular este modo rapidamente. Minhas necessidades resultado final a ser n log (k), mas eu não tenho nenhuma idéia realmente sobre como fazer isso. O mais rápido que eu poderia encontrar era n k ...

Answer 1

Use uma tabela hash para contar a freqüência de cada valor:

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

Conjunto m = n / k arredondado para cima. Fazer um quicksort, mas sublists descarte de comprimento inferior a m.

Como quicksort, você pode ter má sorte e repetidamente escolher pivôs que perto das extremidades. Mas isso tem uma pequena probabilidade de acontecer, se você escolher os pivôs aleatoriamente.

Haverá O (log K) () níveis para a recursividade, e cada nível leva tempo O (n).

Answer 3

Basta caminhar a matriz e manter a contagem em um hash / dicionário (e retornando true uma vez n / k é encontrada, senão false) seria O (n)

editar, algo como:

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

Cálculo Modo de Estatística na F # .net para conjunto de dados (inteiros) que tem única Modo

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

Pseudocódigo:

 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

Assumindo que sua implementação hashtable tem O (1) insert / lookup este deve ser O (n)