Encuentre la diferencia de goles para el máximo de victorias y el equipo reciente con esa diferencia de goles

Geek es un gran fanático de la liga de fútbol. Recientemente ha recibido un documento que contiene los resultados de todos los partidos jugados en la Liga hasta la fecha. Como el número de partidos que se han jugado es demasiado grande, ha seleccionado al azar N partidos cuyos resultados va a analizar. Cada partido tiene el formato { HT HG AT AG} (donde HT es el equipo local, HG es el gol local, AT es el equipo visitante, AG el gol visitante). Geek quiere encontrar la diferencia de goles (GD) [es decir, (goles anotados por el equipo ganador – goles anotados por el equipo perdedor)] por el número máximo de veces que un equipo local ha ganado un partido. Next Geek también quiere encontrar el nombre del equipo que ganó más recientemente un partido en casa de este GD. Sin embargo, Geek es muy perezoso y pide tu ayuda. ¿Puedes ayudar a Geek con su análisis?
En caso de que ningún equipo local haya ganado en ninguno de los N juegos, solo se genera -1.

Nota: Un empate, es decir. Ambos equipos han marcado el mismo número de goles se considera una victoria para el equipo local con GD = 0 .

Ejemplo:

Entrada: N = 4
mumbai 3 goa 2
bengaluru 1 kerala 0
goa 4 hyderabad 5
bengala 3 goa 1
Salida: 1 bengaluru
Explicación: La diferencia de goles por la que un equipo local gana el tiempo máximo es 1.
Mumbai y Bengaluru ganan por diferencia de goles 1, Bengala gana con diferencia de goles 1.
El equipo local en ganar más recientemente con GD = 1, es bengaluru.

Entrada:
N = 3
mumbai 2 Kerala 3
mumbai 6 goa 3
goa 2 bengala 4
Salida: 3 mumbai

 

Enfoque: el problema se puede resolver con la ayuda de hashing utilizando la siguiente idea:

Tome dos mapas hash , el primero almacenará el GD (diferencia de goles) no negativo, es decir, HG (gol local) – AG (objetivo de llegada), y el equipo más reciente en ganar por ese GD . Y el segundo mapa hash almacenará el GD y la frecuencia correspondiente. Si no hay GD no negativo , la salida será -1 .

Siga los pasos que se mencionan a continuación para implementar el enfoque:

  • Cree dos mapas para almacenar la frecuencia y la diferencia de goles como se muestra arriba.
  • Iterar el resultado de N coincidencias:
    • Obtener la diferencia de goles (es decir, GD = HG – AG ).
    • Si el valor no es negativo , gana el equipo local.
    • Si el GD ya está presente en el mapa, actualice el equipo correspondiente para almacenar el equipo más reciente con tanta diferencia de goles.
    • Incrementa la frecuencia de GD .
  • Devuelve el GD con mayor frecuencia y el equipo asociado a él. 

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the name of the team
// which has most recently won a home match
// by this GD
void solve(vector<string>& HT, vector<int>& HG,
           vector<string>& AT, vector<int>& AG)
{
    int N = HG.size();
 
    // Hash map to store gd and its frequency
    unordered_map<int, int> gd_freq;
 
    // Hash map to store gd and
    // the recent home team to win
    // with that gd
    unordered_map<int, string> gd_team;
 
    // Inserting league data in hash maps
    for (int i = 0; i < N; i++) {
        int gd = HG[i] - AG[i];
        if (gd >= 0) {
            gd_freq[gd]++;
            gd_team[gd] = HT[i];
        }
    }
 
    // Stores gd with maximum frequency
    int max_index = 0;
 
    // Stores maximum frequency
    int max_freq = -1;
    for (auto itr = gd_freq.begin();
         itr != gd_freq.end();
         itr++) {
 
        // To find maximum frequency
        // and the corresponding gd
        if (max_freq <= itr->second) {
            max_freq = itr->second;
            max_index = itr->first;
        }
    }
 
    // If no home team has won
    if (max_freq == -1) {
        cout << "-1";
    }
    else {
        cout << max_index << " " << gd_team[max_index];
    }
}
 
// Driver Code
int main()
{
    int N = 4;
 
    // Store home teams
    vector<string> HT
        = { "mumbai", "bengaluru", "goa", "bengal" };
 
    // Store goals by home teams
    vector<int> HG = { 3, 1, 4, 3 };
 
    // Store arrival teams
    vector<string> AT
        = { "goa", "kerala", "hyderabad", "goa" };
 
    // Store goals by home teams
    vector<int> AG = { 2, 0, 5, 1 };
 
    // Function call
    solve(HT, HG, AT, AG);
    return 0;
}

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the name of the team
    // which has most recently won a home match
    // by this GD
    public static void solve(String HT[], int HG[],
                             String AT[], int AG[])
    {
        int N = 4;
 
        // Hash map to store gd and its frequency
        Map<Integer, Integer> gd_freq
            = new HashMap<Integer, Integer>();
 
        // Hash map to store gd and
        // the recent home team to win
        // with that gd
        Map<Integer, String> gd_team
            = new HashMap<Integer, String>();
 
        // Inserting league data in hash maps
        for (int i = 0; i < N; i++) {
            int gd = HG[i] - AG[i];
            if (gd >= 0) {
                int prev_freq = 0;
                if (gd_freq.get(gd) != null) {
                    prev_freq = gd_freq.get(gd);
                }
                gd_freq.put(gd, prev_freq + 1);
                gd_team.put(gd, HT[i]);
            }
        }
 
        // Stores gd with maximum frequency
        int max_index = 0;
 
        // Stores maximum frequency
        int max_freq = -1;
        for (Map.Entry<Integer, Integer> entry :
             gd_freq.entrySet()) {
 
            // To find maximum frequency and the
            // corresponding gd
            if (max_freq <= entry.getValue()) {
                max_freq = entry.getValue();
                max_index = entry.getKey();
            }
        }
 
        // If no home team has won
        if (max_freq == -1) {
            System.out.println("-1");
        }
        else {
            System.out.println(max_index + " "
                               + gd_team.get(max_index));
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4;
 
        // Store home teams
        String HT[]
            = { "mumbai", "bengaluru", "goa", "bengal" };
 
        // Store goals by home teams
        int HG[] = { 3, 1, 4, 3 };
 
        // Store arrival teams
        String AT[]
            = { "goa", "kerala", "hyderabad", "goa" };
 
        // Store goals by home teams
        int AG[] = { 2, 0, 5, 1 };
 
        // Function call
        solve(HT, HG, AT, AG);
    }
}

Python3

# Python3 code to implement the approach
 
# Function to find the name of the team
# which has most recently won a home match
# by this GD
def solve(HT, HG, AT, AG) :
 
    N = len(HG);
 
    # Hash map to store gd and its frequency
    gd_freq = {};
 
    # Hash map to store gd and
    # the recent home team to win
    # with that gd
    gd_team = {};
 
    # Inserting league data in hash maps
    for i in range(N) :
        gd = HG[i] - AG[i];
         
        if (gd >= 0) :
            gd_freq[gd] = gd_freq.get(gd,0) + 1;
            gd_team[gd] = HT[i];
 
    # Stores gd with maximum frequency
    max_index = 0;
 
    # Stores maximum frequency
    max_freq = -1;
    for itr in gd_freq :
 
        # To find maximum frequency
        # and the corresponding gd
        if (max_freq <= gd_freq[itr]) :
            max_freq = gd_freq[itr];
            max_index = itr;
 
    # If no home team has won
    if (max_freq == -1) :
        print("-1");
     
    else :
        print(max_index," ",gd_team[max_index]);
 
 
# Driver Code
if __name__ == "__main__" :
 
    N = 4;
 
    # Store home teams
    HT = [ "mumbai", "bengaluru", "goa", "bengal" ];
 
    # Store goals by home teams
    HG = [ 3, 1, 4, 3 ];
 
    # Store arrival teams
    AT = [ "goa", "kerala", "hyderabad", "goa" ];
 
    # Store goals by home teams
    AG = [ 2, 0, 5, 1 ];
 
    # Function call
    solve(HT, HG, AT, AG);
     
    # This code is contributed by AnkThon

C#

// C# code to implement the approach
using System;
 
// class to store gd frequency and
// the recent home team
class GFG
{
    public class goalDiff
    {
        public int frequency;
        public String team_name;
    }
 
    // Function to find the team and
    // the goal difference
    static void solve(String[] HT, int[] HG,
                      String[] AT, int[] AG)
    {
        int MAX = 100;
        int N = 4;
 
        // Hash map to store gd, its frequency and
        // the recent home team to win with that gd
        goalDiff[] arr = new goalDiff[MAX];
        for (int i = 0; i < MAX; i++)
        {
            arr[i] = new goalDiff();
            arr[i].frequency = 0;
            arr[i].team_name = "";
        }
 
        // Inserting league data in hash maps
        for (int i = 0; i < N; i++)
        {
            int gd = HG[i] - AG[i];
            if (gd >= 0)
            {
                arr[gd].frequency++;
                arr[gd].team_name = HT[i];
            }
        }
 
        // Stores gd with maximum frequency
        int max_index = 0;
 
        // Stores maximum frequency
        int max_freq = -1;
        for (int i = 0; i < MAX; i++)
        {
 
            // To find maximum frequency and
            // the corresponding gd
            if (max_freq <= arr[i].frequency)
            {
                max_freq = arr[i].frequency;
                max_index = i;
            }
        }
 
        // If no home team has won
        if (max_freq == -1)
        {
            Console.WriteLine("-1");
        }
        else
        {
            Console.WriteLine(max_index + " "
                               + arr[max_index].team_name);
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 4;
 
        // Store home teams
        String[] HT = { "mumbai", "bengaluru", "goa", "bengal" };
 
        // Store goals by home teams
        int[] HG = { 3, 1, 4, 3 };
 
        // Store arrival teams
        String[] AT = { "goa", "kerala", "hyderabad", "goa" };
 
        // Store goals by home teams
        int[] AG = { 2, 0, 5, 1 };
 
        // Function call
        solve(HT, HG, AT, AG);
    }
}
 
// This code is contributed by saurabh_jaiswal.

Javascript

//JS code to implement the approach
 
// Function to find the name of the team
// which has most recently won a home match
// by this GD
function solve(HT, HG, AT, AG)
{
    var N = HG.length;
 
    // Hash map to store gd and its frequency
    var gd_freq = {};
 
    // Hash map to store gd and
    // the recent home team to win
    // with that gd
    var gd_team = {};
 
    // Inserting league data in hash maps
    for (var i = 0; i < N; i++)
    {
        var gd = HG[i] - AG[i];
         
        if (gd >= 0)
        {
            if (!gd_freq.hasOwnProperty(gd))
                gd_freq[gd] = 1;
            else
                gd_freq[gd] = gd_freq[gd] + 1;
            gd_team[gd] = HT[i];
        }
    }
 
    // Stores gd with maximum frequency
    var max_index = 0;
 
    // Stores maximum frequency
    var max_freq = -1;
     
    for (const itr in gd_freq)
    {
        // To find maximum frequency
        // and the corresponding gd
        if (max_freq <= gd_freq[itr])
        {
            max_freq = gd_freq[itr];
            max_index = itr;
        }
    }
    // If no home team has won
    if (max_freq == -1)
        console.log("-1");
     
    else
        console.log(max_index, gd_team[max_index]);
}
 
 
// Driver Code
var N = 4;
 
// Store home teams
var HT = [ "mumbai", "bengaluru", "goa", "bengal" ];
 
// Store goals by home teams
var HG = [ 3, 1, 4, 3 ];
 
// Store arrival teams
var AT = [ "goa", "kerala", "hyderabad", "goa" ];
 
// Store goals by home teams
var AG = [ 2, 0, 5, 1 ];
 
// Function call
solve(HT, HG, AT, AG);
     
// This code is contributed by phasing17
Producción

1 bengaluru

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Enfoque alternativo: el problema también se puede resolver basándose en el concepto de clase y estructura según la siguiente idea:

Cree una estructura o clase con objetos como frecuencia y nombre_equipo (que almacenará el equipo más reciente que ganó con esa diferencia de goles). Cree una array de la estructura o clase declarada con la diferencia de objetivos máxima posible como su tamaño, que funcionará como una tabla hash donde la diferencia de objetivos es la clave.

Siga los pasos mencionados a continuación para implementar la idea:

  • Cree una clase o estructura como se mencionó anteriormente y una array (digamos arr[] ) de esa clase o estructura.
  • Iterar sobre todos los registros del partido:
    • Calcule la diferencia de goles (es decir, GD = HG – AG ).
    • Si GD no es negativo, gana el equipo local.
    • Complete arr[GD] con la frecuencia actualizada y el nombre del equipo actual, ya que este es el equipo que ganará el partido con una diferencia de goles de GD .
  • Ahora iterar arr[] :
    • Si la frecuencia en arr[i] es la máxima, actualice la frecuencia máxima y el equipo asociado con los datos de arr[i].
  • Devuelve la frecuencia máxima y el equipo asociado con eso como respuesta.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Maximum possible goal difference
#define MAX 100
 
// Structure with frequency
// and recent team name
struct goalDiff {
    int frequency;
    string team_name;
};
 
// Function to find the team
// and the goal difference
void solve(vector<string>& HT, vector<int>& HG,
           vector<string>& AT, vector<int>& AG)
{
    int N = 4;
 
    // Array to store gd, its frequency and
    // the recent home team to win with that gd
    goalDiff arr[MAX];
    for (int i = 0; i < MAX; i++) {
        arr[i].frequency = 0;
        arr[i].team_name = "";
    }
 
    // Inserting league data in hash maps
    for (int i = 0; i < N; i++) {
        int gd = HG[i] - AG[i];
        if (gd >= 0) {
            arr[gd].frequency++;
            arr[gd].team_name = HT[i];
        }
    }
 
    int max_index = 0;
    int max_freq = -1;
    for (int i = 0; i < MAX; i++) {
 
        // To find maximum frequency and
        // the corresponding gd
        if (max_freq <= arr[i].frequency) {
            max_freq = arr[i].frequency;
            max_index = i;
        }
    }
 
    // If no home team has won
    if (max_freq == 0) {
        cout << "-1";
    }
    else {
        cout << max_index << " "
             << arr[max_index].team_name;
    }
}
 
// Driver Code
int main()
{
    int N = 4;
 
    // Store home teams
    vector<string> HT
        = { "mumbai", "bengaluru", "goa", "bengal" };
 
    // Store goals by home teams
    vector<int> HG = { 3, 1, 4, 3 };
 
    // Store arrival teams
    vector<string> AT
        = { "goa", "kerala", "hyderabad", "goa" };
 
    // store goals by home teams
    vector<int> AG = { 2, 0, 5, 1 };
 
    // Function call
    solve(HT, HG, AT, AG);
    return 0;
}

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
// class to store gd frequency and
// the recent home team
class goalDiff {
    int frequency;
    String team_name;
}
 
class Main {
 
    // Function to find the team and
    // the goal difference
    static void solve(String HT[], int HG[],
                      String AT[], int AG[])
    {
        int MAX = 100;
        int N = 4;
 
        // Hash map to store gd, its frequency and
        // the recent home team to win with that gd
        goalDiff arr[] = new goalDiff[MAX];
        for (int i = 0; i < MAX; i++) {
            arr[i] = new goalDiff();
            arr[i].frequency = 0;
            arr[i].team_name = "";
        }
 
        // Inserting league data in hash maps
        for (int i = 0; i < N; i++) {
            int gd = HG[i] - AG[i];
            if (gd >= 0) {
                arr[gd].frequency++;
                arr[gd].team_name = HT[i];
            }
        }
 
        // Stores gd with maximum frequency
        int max_index = 0;
 
        // Stores maximum frequency
        int max_freq = -1;
        for (int i = 0; i < MAX; i++) {
 
            // To find maximum frequency and
            // the corresponding gd
            if (max_freq <= arr[i].frequency) {
                max_freq = arr[i].frequency;
                max_index = i;
            }
        }
 
        // If no home team has won
        if (max_freq == -1) {
            System.out.println("-1");
        }
        else {
            System.out.println(max_index + " "
                               + arr[max_index].team_name);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4;
 
        // Store home teams
        String HT[]
            = { "mumbai", "bengaluru", "goa", "bengal" };
 
        // Store goals by home teams
        int HG[] = { 3, 1, 4, 3 };
 
        // Store arrival teams
        String AT[]
            = { "goa", "kerala", "hyderabad", "goa" };
 
        // Store goals by home teams
        int AG[] = { 2, 0, 5, 1 };
 
        // Function call
        solve(HT, HG, AT, AG);
    }
}

Python3

# Python3 code to implement the approach
 
# Maximum possible goal difference
MAX = 100
 
# class with frequency
# and recent team name
class goalDiff:
    def __init__(self,frequency,team_name):
        self.frequency = frequency
        self.team_name = team_name
     
# Function to find the team
# and the goal difference
def solve(HT, HG, AT, AG):
    global MAX
    N = 4
 
    # Array to store gd, its frequency and
    # the recent home team to win with that gd
    arr = [0 for i in range(MAX)]
    for i in range(MAX):
        arr[i] = goalDiff(0,"")
 
    # Inserting league data in hash maps
    for i in range(N):
        gd = HG[i] - AG[i]
        if (gd >= 0):
            arr[gd].frequency += 1
            arr[gd].team_name = HT[i]
 
    max_index = 0
    max_freq = -1
    for i in range(MAX):
 
        # To find maximum frequency and
        # the corresponding gd
        if (max_freq <= arr[i].frequency):
            max_freq = arr[i].frequency
            max_index = i
 
    # If no home team has won
    if (max_freq == 0):
        print("-1")
    else:
        print(f"{max_index} {arr[max_index].team_name}")
     
# Driver Code
N = 4
 
# Store home teams
HT = [ "mumbai", "bengaluru", "goa", "bengal" ]
 
# Store goals by home teams
HG = [ 3, 1, 4, 3 ]
 
# Store arrival teams
AT = [ "goa", "kerala", "hyderabad", "goa" ]
 
# store goals by home teams
AG = [ 2, 0, 5, 1 ]
 
# Function call
solve(HT, HG, AT, AG)
 
# This code is contributed by shinjanpatra

C#

// C# code to implement the approach
 
using System;
 
// class to store gd frequency and
// the recent home team
class goalDiff {
    public int frequency;
    public string team_name;
}
 
class GFG {
 
    // Function to find the team and
    // the goal difference
    static void solve(string[] HT, int[] HG, string[] AT,
                      int[] AG)
    {
        int MAX = 100;
        int N = 4;
 
        // Hash map to store gd, its frequency and
        // the recent home team to win with that gd
        goalDiff[] arr = new goalDiff[MAX];
        for (int i = 0; i < MAX; i++) {
            arr[i] = new goalDiff();
            arr[i].frequency = 0;
            arr[i].team_name = "";
        }
 
        // Inserting league data in hash maps
        for (int i = 0; i < N; i++) {
            int gd = HG[i] - AG[i];
            if (gd >= 0) {
                arr[gd].frequency++;
                arr[gd].team_name = HT[i];
            }
        }
 
        // Stores gd with maximum frequency
        int max_index = 0;
 
        // Stores maximum frequency
        int max_freq = -1;
        for (int i = 0; i < MAX; i++) {
 
            // To find maximum frequency and
            // the corresponding gd
            if (max_freq <= arr[i].frequency) {
                max_freq = arr[i].frequency;
                max_index = i;
            }
        }
 
        // If no home team has won
        if (max_freq == -1) {
            Console.WriteLine("-1");
        }
        else {
            Console.WriteLine(max_index + " "
                              + arr[max_index].team_name);
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
 
        // Store home teams
        string[] HT
            = { "mumbai", "bengaluru", "goa", "bengal" };
 
        // Store goals by home teams
        int[] HG = { 3, 1, 4, 3 };
 
        // Store arrival teams
        string[] AT
            = { "goa", "kerala", "hyderabad", "goa" };
 
        // Store goals by home teams
        int[] AG = { 2, 0, 5, 1 };
 
        // Function call
        solve(HT, HG, AT, AG);
    }
}
 
// This code is contributed by phasing17

Javascript

<script>
 
// JavaScript code to implement the approach
 
 
// Maximum possible goal difference
const MAX = 100
 
// class with frequency
// and recent team name
class goalDiff {
    constructor(frequency,team_name){
    this.frequency = frequency;
    this.team_name = team_name;
    }
}
 
// Function to find the team
// and the goal difference
function solve(HT, HG, AT, AG)
{
    let N = 4;
 
    // Array to store gd, its frequency and
    // the recent home team to win with that gd
    let arr = new Array(MAX);
    for (let i = 0; i < MAX; i++) {
        arr[i] = new goalDiff(0,"")
    }
 
    // Inserting league data in hash maps
    for (let i = 0; i < N; i++) {
        let gd = HG[i] - AG[i];
        if (gd >= 0) {
            arr[gd].frequency++;
            arr[gd].team_name = HT[i];
        }
    }
 
    let max_index = 0;
    let max_freq = -1;
    for (let i = 0; i < MAX; i++) {
 
        // To find maximum frequency and
        // the corresponding gd
        if (max_freq <= arr[i].frequency) {
            max_freq = arr[i].frequency;
            max_index = i;
        }
    }
 
    // If no home team has won
    if (max_freq == 0) {
        document.write("-1","</br>");
    }
    else {
        document.write(max_index," ",arr[max_index].team_name,"</br>");
    }
}
 
// Driver Code
 
let N = 4;
 
// Store home teams
let HT = [ "mumbai", "bengaluru", "goa", "bengal" ];
 
// Store goals by home teams
let HG = [ 3, 1, 4, 3 ];
 
// Store arrival teams
let AT = [ "goa", "kerala", "hyderabad", "goa" ];
 
// store goals by home teams
let AG = [ 2, 0, 5, 1 ];
 
// Function call
solve(HT, HG, AT, AG);
 
// This code is contributed by shinjanpatra
 
</script>
Producción

1 bengaluru

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por sachin801 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *