algorithm - resueltos - profe alex medidas de tendencia central

Computando el modo estadístico

Question

Actualmente estoy tratando de verificar si, dado un conjunto desordenado A de longitud N y un número entero k, existe algún elemento que ocurra n / k veces o más.

Mi pensamiento para este problema fue calcular el modo y luego comparar esto con n / k. Sin embargo, no sé cómo calcular este modo rápidamente. Mi resultado final debe ser n log (k), pero realmente no tengo idea de cómo hacerlo. Lo más rápido que pude encontrar fue n k ...

Answer 1

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

Suponiendo que su implementación hashtable tiene O (1) insertar / buscar esto debería ser O (n)

Answer 2

Set m = n / k redondeado hacia arriba. Haz un quicksort, pero descarta sublistas de longitud inferior a m.

Al igual que el quicksort, puede tener mala suerte y elegir repetidamente pivotes que se acerquen a los extremos. Pero esto tiene una pequeña probabilidad de suceder, si eliges los pivotes aleatoriamente.

Habrá niveles O (log (k)) para la recursión, y cada nivel toma O (n) tiempo.

Answer 3

Simplemente caminando por la matriz y manteniendo los recuentos en un hash / diccionario (y retornando verdadero una vez que se encuentra n / k, de lo contrario es falso) sería O (n)

editar, algo así 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

Use una tabla hash para contar la frecuencia 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 5

Cálculo del modo estadístico en F # .net para conjunto de datos (enteros) que tiene modo único

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