Encuentre quién ganó la elección según el sistema de votación dado

Dada una array de pares arr[][] de la forma {X, Y} tal que cada arr[i] representa el momento X en el que se votó al candidato con ID de candidato Y y una array de consultas query[] que consta de M enteros positivos, la tarea de cada consulta Q[i] es encontrar el ID del candidato ganador en ese momento Q[i] de la votación.

Nota: En caso de que haya 2 candidatos con el mismo número de votos K en un momento dado, imprima el candidato que obtuvo esos votos primero.

Ejemplos:

Entrada: arr[] = {{1, 2}, {2, 2}, {4, 1}, {5, 5}, {7, 1}, {11, 1}}, consulta[] = {2 , 8, 12}
Salida: 2 2 1
Explicación:
Para consulta[0] = 2, en el momento 2, el candidato con ID de candidato = 2 tiene el máximo de votos.
Para consulta[1] = 8, en el momento 8, los candidatos con ID de candidato = 2 y 1 obtuvieron el máximo de votos, es decir, 2, pero como el candidato con ID 2 los obtuvo antes, la respuesta es 2.
Para consulta[2] = 12 , en el momento 12, el candidato con ID de candidato = 1 tiene el máximo de votos, es decir, 3.

Entrada: arr[] = {{1, 1}}, consulta[] = { 1 }
Salida: 1

Enfoque: el problema dado se puede resolver precalculando el ganador en cada intervalo de tiempo en la array arr[] y almacenándolo en otra array, digamos Ans[] en forma de {timeInterval, winnerCandidateID} y luego para cada consulta consulta[ i] realice la búsqueda binaria en la array Ans[] para obtener el candidato ganador en el momento de la consulta[i] . Siga los pasos a continuación para resolver el problema:

• Inicialice un vector , digamos Ans[] que almacena el ganador en cada intervalo de tiempo entrante arr[i].primero .
• Inicialice un mapa desordenado , digamos Map[] que almacena la frecuencia de la identificación del candidato en cada intervalo de tiempo entrante.
• Inicialice un par , digamos anterior[] que realiza un seguimiento del candidato ganador.
• Empuje el primer par en el vector Ans[] y márquelo como el anterior.
• Iterar sobre el rango [1, N – 1] usando la variable i y realizar los siguientes pasos:
  • Incremente la frecuencia del candidato actual arr[i].segundo en 1 en el mapa Map .
  • Si el candidato actual gana hasta ahora, actualice el par anterior .
  • Inserta el anterior en el vector Ans[] .
• Iterar sobre el rango [0, M) usando la variable i y realizar los siguientes pasos:
  • Para cada consulta, realice una búsqueda binaria en el vector de pares Ans[] para encontrar el candidato ganador.
  • Realice la búsqueda binaria en el tiempo, es decir, el primer valor del vector de pares Ans[] y encuentre el valor más grande que es menor que igual a query[ I ] , e imprima el ID de candidato correspondiente .

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

// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
 
// Function to perform binary search
// to find the candidate with most votes
// for a particular time
int binarySearch(vector<pair<int, int> >& Ans, int low,
                 int high, int value)
{
    // Base Cases
    if (value <= Ans[low].first)
        return Ans[low].second;
    if (value >= Ans[high].first)
        return Ans[high].second;
 
    int winningCandidate;
 
    while (low <= high) {
 
        // Find the mid
        int mid = low + (high - low) / 2;
 
        // If the value at mid is the
        // result
        if (Ans[mid].first == value) {
            winningCandidate = Ans[mid].second;
            break;
        }
 
        // Update the ranges
        else if (Ans[mid].first < value) {
            winningCandidate = Ans[mid].second;
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
 
    return winningCandidate;
}
 
// Function to find the winner for each query
void findWinner(pair<int, int> arr[], int N, int query[],
                int M)
{
 
    // Map to store the frequency
    unordered_map<int, int> Map;
 
    // Stores the winning candidate till
    // a particular time
    vector<pair<int, int> > Ans;
 
    // Starting Reference
    pair<int, int> previous
        = { arr[0].first, arr[0].second };
    Ans.push_back(previous);
    Map[arr[0].second]++;
 
    // Iterate over the range
    for (int i = 1; i < N; i++) {
 
        // Increase the frequency
        Map[arr[i].second]++;
 
        // Update the reference if another
        // candidate gets more votes than
        // the one considered
        if (Map[arr[i].second] > Map[previous.second]) {
            previous.second = arr[i].second;
        }
 
        previous.first = arr[i].first;
 
        // Push into the vector
        Ans.push_back(previous);
    }
 
    // Iterate over the range
    for (int i = 0; i < M; i++) {
        cout << binarySearch(Ans, 0, N - 1, query[i])
             << ' ';
    }
}
 
// Driver Code
int main()
{
    pair<int, int> arr[]
        = { { 1, 2 }, { 2, 2 }, { 4, 1 },
            { 5, 5 }, { 7, 1 }, { 11, 1 } };
    int query[] = { 2, 8, 12 };
    int N = 6;
    int M = 3;
 
    findWinner(arr, N, query, M);
 
    return 0;
}

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to perform binary search
# to find the candidate with most votes
# for a particular time
def binarySearch(Ans,
                 low,  high,  value):
 
    # Base Cases
    if (value <= Ans[low][0]):
        return Ans[low][1]
    if (value >= Ans[high][0]):
        return Ans[high][1]
 
    while (low <= high):
 
        # Find the mid
        mid = low + (high - low) // 2
 
        # If the value at mid is the
        # result
        if (Ans[mid][0] == value):
            winningCandidate = Ans[mid][1]
            break
 
        # Update the ranges
        elif (Ans[mid][0] < value):
            winningCandidate = Ans[mid][1]
            low = mid + 1
 
        else:
            high = mid - 1
 
    return winningCandidate
 
# Function to find the winner for each query
 
 
def findWinner(arr,
               N,  query,
               M):
 
    # Map to store the frequency
    Map = defaultdict(int)
 
    # Stores the winning candidate till
    # a particular time
    Ans = []
 
    # Starting Reference
    previous = [arr[0][0], arr[0][1]]
    Ans.append([previous[0], previous[1]])
    Map[arr[0][1]] += 1
 
    # Iterate over the range
    for i in range(1, N):
 
        # Increase the frequency
        Map[arr[i][1]] += 1
 
        # Update the reference if another
        # candidate gets more votes than
        # the one considered
        if (Map[arr[i][1]]
                > Map[previous[1]]):
            previous[1] = arr[i][1]
 
        previous[0] = arr[i][0]
 
        # Push into the vector
        Ans.append([previous[0], previous[1]])
 
    # Iterate over the range
    for i in range(M):
        print(binarySearch(
            Ans, 0, N - 1, query[i]), end=' ')
 
# Driver Code
if __name__ == "__main__":
 
    arr = [[1, 2], [2, 2], [4, 1],
           [5, 5], [7, 1], [11, 1]]
    query = [2, 8, 12]
    N = 6
    M = 3
 
    findWinner(arr, N, query, M)
 
    # This code is contributed by ukasp.

2 2 1

Complejidad de tiempo: O(max(N, M*log(N)))
Espacio auxiliar: O(N)