Hoy estaba resolviendo el siguiente problema (desafortunadamente no logré una mayor complejidad de tiempo requerida).

Dada una lista de puntajes de los exámenes de los estudiantes, encuentre la mejor calificación promedio. Cada estudiante puede tener más de un puntaje en la lista, y la mejor calificación promedio es el promedio de todos los puntajes de ese estudiante. Complete la función bestAverageGrade en el editor a continuación. Tiene un parámetro, puntajes, que es un conjunto de puntajes de exámenes de estudiantes. Cada elemento de la matriz es una matriz de dos elementos de la forma [nombre del alumno, puntaje de la prueba] p. Ej. ["Bobby", "87"]. Se otorgarán más puntos por soluciones que puedan manejar entradas más grandes dentro de un período de tiempo establecido, es decir, código con una complejidad de tiempo de ejecución más rápida.

Formato de entrada

Las puntuaciones de los parámetros de entrada son una matriz de matrices, donde cada sub-matriz contiene dos cadenas: el nombre del alumno seguido de una calificación de prueba como una cadena. También debe incluir el número de entradas y el tamaño de cada entrada (siempre será 2). Ver abajo para ejemplos específicos. Los puntajes de los exámenes pueden ser enteros positivos o negativos.

Formato de salida

Su función debe devolver un número entero único que represente la mejor calificación promedio. Si termina con una calificación promedio que no es un número entero, debe usar una función de piso para devolver el número entero más grande menor o igual que el promedio.

Devuelve 0 para una entrada vacía.

Entrada de muestra 0

[ [ "Bobby", "87" ],
  [ "Charles", "100" ],
  [ "Eric", "64" ],
  [ "Charles", "22" ] ]

Ingresado como

4 2 Bobby 87 Charles 100 Eric 64 Charles 22

Salida de muestra 0 87

Y aquí está mi método bestAverageGrade:

def bestAverageGrade(scores):
    list_of_students = set([x[0] for x in scores])
    averages = []
    for student in list_of_students:
        results = [float(x[1]) for x in scores if x[0] == student]
        averages.append(sum(results_of_student)/len(results))
    return math.floor(max(averages))

¿Cómo podría lograr una mejor complejidad del tiempo? Sé que ahora la lista de listas se repite dos veces.

-1
walkerous 27 ene. 2018 a las 18:34

2 respuestas

La mejor respuesta

Repite la lista varias veces: una vez para cada alumno. Si hay varios estudiantes, el número de ciclos puede ser bastante grande, por lo que la complejidad del tiempo puede ser, en el peor de los casos, O (n 2 ) .

Podemos utilizar un enfoque en el que, por ejemplo, utilicemos un diccionario. Podemos definir un diccionario grades que mapea el nombre de cada estudiante en una tupla de 2 (un numerador y un denominador). En ese caso, el código se ve así:

Pitón vainilla

def bestAverageGrade(scores):
    grades = {}
    for student, grade in scores:
        grade = float(grade)
        current = grades.get(student)
        if current is None:
            grades[student] = grade, 1
        else:
            num, denom = current
            grades[student] = num + grade, denom + 1
    return math.floor(max(num/denom for num, denom in grades.values()))

Pandas

También podemos aumentar el rendimiento usando Pandas. Por ejemplo:

import pandas as pd

def bestAverageGrade(scores):
    df = pd.DataFrame([[name, float(score)] for name, score in scores],
                      columns=['student', 'score'])
    return math.floor(df.groupby('student')['score'].mean().max())

Entonces, aquí primero agrupamos por estudiantes y tomamos la media como un agregado para la columna 'score'. Entonces tomamos el máximo sobre todos estos estudiantes.

0
Willem Van Onsem 27 ene. 2018 a las 15:48

Uso de Javascript.

function bestAverageGrade(scores) {
          if(!Array.isArray(scores) || scores.length === 0) return 0;
          let duplicateFrequency = {};
          let sumFrequency = {};
          scores.forEach(item =>  {
            duplicateFrequency[item[0]] = duplicateFrequency[item[0]] ? duplicateFrequency[item[0]]+1 : 1;
         sumFrequency[item[0]] = sumFrequency[item[0]] ? sumFrequency[item[0]]+Number(item[1]) : Number(item[1]);
    })
      for( let props in duplicateFrequency) {
        sumFrequency[props] = Math.floor(sumFrequency[props] / duplicateFrequency[props])
      }

     return Math.max(...Object.values(sumFrequency))
    }

La complejidad del tiempo aquí es O (n)

Enfoque: aquí usamos dos hashMaps, uno para almacenar los duplicados y el otro para almacenar las calificaciones totales de cada estudiante.

Entonces solo estamos reflexionando sobre uno de los hashMaps y dividiendo la suma total con los duplicados. Suelo del resultado para evitar decimales.

Finalmente, use Math.max para obtener el valor máximo.

0
Akash Chakroborty 3 abr. 2020 a las 14:28