Encuentre el ganador de una elección donde los votos se representan como nombres de candidatos

Dada una serie de nombres de candidatos en una elección. El nombre de un candidato en la array representa un voto emitido sobre el candidato. Escriba el nombre de los candidatos que recibieron el máximo de votos. Si hay empate, escriba un nombre lexicográficamente más pequeño.

Ejemplos: 

Input :  votes[] = {"john", "johnny", "jackie", 
                    "johnny", "john", "jackie", 
                    "jamie", "jamie", "john",
                    "johnny", "jamie", "johnny", 
                    "john"};
Output : John
We have four Candidates with name as 'John', 
'Johnny', 'jamie', 'jackie'. The candidates
John and Johny get maximum votes. Since John
is alphabetically smaller, we print it.

Una solución simple es ejecutar dos bucles y contar las ocurrencias de cada palabra. La complejidad temporal de esta solución es O(n * n * MAX_WORD_LEN).

Una solución eficiente es utilizar Hashing . Insertamos todos los votos en un mapa hash y realizamos un seguimiento de los recuentos de diferentes nombres. Finalmente, recorremos el mapa e imprimimos la persona con el máximo de votos.

Implementación:

C++

// C++++ program to find winner in an election.
#include "bits/stdc++.h"
using namespace std;
 
    /* We have four Candidates with name as 'John',
      'Johnny', 'jamie', 'jackie'.
       The votes in String array are as per the
       votes casted. Print the name of candidates
       received Max vote. */
    void findWinner(vector<string>& votes)
    {
         
        // Insert all votes in a hashmap
        unordered_map<string,int> mapObj ;
        for (auto& str : votes)
        {
            mapObj[str]++;
        }
  
        // Traverse through map to find the candidate
        // with maximum votes.
        int maxValueInMap = 0;
        string winner;
        for (auto& entry : mapObj)
        {
            string key  = entry.first;
            int val = entry.second;
            if (val > maxValueInMap)
            {
                maxValueInMap = val;
                winner = key;
            }
  
            // If there is a tie, pick lexicographically
            // smaller.
            else if (val == maxValueInMap &&
                winner>key)
                winner = key;
        }
        cout << winner << endl;
    }
  
    // Driver code
    int main()
    {
       vector<string> votes = { "john", "johnny", "jackie",
                         "johnny", "john", "jackie",
                         "jamie", "jamie", "john",
                         "johnny", "jamie", "johnny",
                         "john" };
  
       findWinner(votes);
       return 0;
    }
    

Java

// Java program to find winner in an election.
import java.util.*;
 
public class ElectoralVotingBallot
{
    /* We have four Candidates with name as 'John',
      'Johnny', 'jamie', 'jackie'.
       The votes in String array are as per the
       votes casted. Print the name of candidates
       received Max vote. */
    public static void findWinner(String votes[])
    {
        // Insert all votes in a hashmap
        Map<String,Integer> map =
                    new HashMap<String, Integer>();
        for (String str : votes)
        {
            if (map.keySet().contains(str))
                map.put(str, map.get(str) + 1);
            else
                map.put(str, 1);
        }
 
        // Traverse through map to find the candidate
        // with maximum votes.
        int maxValueInMap = 0;
        String winner = "";
        for (Map.Entry<String,Integer> entry : map.entrySet())
        {
            String key  = entry.getKey();
            Integer val = entry.getValue();
            if (val > maxValueInMap)
            {
                maxValueInMap = val;
                winner = key;
            }
 
            // If there is a tie, pick lexicographically
            // smaller.
            else if (val == maxValueInMap &&
                winner.compareTo(key) > 0)
                winner = key;
        }
        System.out.println(winner);
    }
 
    // Driver code
    public static void main(String[] args)
    {
       String[] votes = { "john", "johnny", "jackie",
                         "johnny", "john", "jackie",
                         "jamie", "jamie", "john",
                         "johnny", "jamie", "johnny",
                         "john" };
 
       findWinner(votes);
    }
}

Python3

# Python3 program to find winner in an election.
from collections import defaultdict
 
''' We have four Candidates with name as 'John',
'Johnny', 'jamie', 'jackie'.
The votes in String array are as per the
votes casted. Print the name of candidates
received Max vote. '''
def findWinner(votes):
 
    # Insert all votes in a hashmap
    mapObj = defaultdict(int)
     
    for st in votes:
        mapObj[st] += 1
 
    # Traverse through map to find the
    # candidate with maximum votes.
    maxValueInMap = 0
    winner = ""
     
    for entry in mapObj:
        key = entry
        val = mapObj[entry]
         
        if (val > maxValueInMap):
            maxValueInMap = val
            winner = key
 
        # If there is a tie, pick lexicographically
        # smaller.
        else if (val == maxValueInMap and
              winner > key):
            winner = key
 
    print(winner)
 
# Driver code
if __name__ == "__main__":
 
    votes = [ "john", "johnny", "jackie",
              "johnny", "john", "jackie",
              "jamie", "jamie", "john",
              "johnny", "jamie", "johnny",
              "john" ]
 
    findWinner(votes)
 
# This code is contributed by ukasp

C#

// C# program to find winner in an election.
using System;
using System.Collections.Generic;
 
public class ElectoralVotingBallot
{
    /* We have four Candidates with name as 'John',
    'Johnny', 'jamie', 'jackie'.
    The votes in String array are as per the
    votes casted. Print the name of candidates
    received Max vote. */
    public static void findWinner(String []votes)
    {
        // Insert all votes in a hashmap
        Dictionary<String,int> map =
                    new Dictionary<String, int>();
        foreach (String str in votes)
        {
            if (map.ContainsKey(str))
                map[str] = map[str] + 1;
            else
                map.Add(str, 1);
        }
 
        // Traverse through map to find the candidate
        // with maximum votes.
        int maxValueInMap = 0;
        String winner = "";
        foreach(KeyValuePair<String, int> entry in map)
        {
            String key = entry.Key;
            int val = entry.Value;
            if (val > maxValueInMap)
            {
                maxValueInMap = val;
                winner = key;
            }
 
            // If there is a tie, pick lexicographically
            // smaller.
            else if (val == maxValueInMap &&
                winner.CompareTo(key) > 0)
                winner = key;
        }
        Console.WriteLine(winner);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String[] votes = { "john", "johnny", "jackie",
                            "johnny", "john", "jackie",
                            "jamie", "jamie", "john",
                            "johnny", "jamie", "johnny",
                            "john" };
     
        findWinner(votes);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program to find winner in an election.
     
    /* We have four Candidates with name as 'John',
      'Johnny', 'jamie', 'jackie'.
       The votes in String array are as per the
       votes casted. Print the name of candidates
       received Max vote. */
    function findWinner(votes)
    {
        let map = new Map();
        for(let i=0;i<votes.length;i++)
        {
            if(map.has(votes[i]))
            {
                map.set(votes[i], map.get(votes[i]) + 1);
            }
             
            else
                map.set(votes[i], 1);
        }
         
        // Traverse through map to find the candidate
        // with maximum votes.
        let maxValueInMap = 0;
        let winner = "";
        for (let [key, value] of map.entries())
        {
            let Key  = key;
            let val = value;
            if (val > maxValueInMap)
            {
                maxValueInMap = val;
                winner = key;
            }
  
            // If there is a tie, pick lexicographically
            // smaller.
            else if (val == maxValueInMap &&
                winner>Key)
                winner = Key;
        }
        document.write(winner);
                     
    }
     
    // Driver code
    let votes=["john", "johnny", "jackie",
                         "johnny", "john", "jackie",
                         "jamie", "jamie", "john",
                         "johnny", "jamie", "johnny",
                         "john"];
    findWinner(votes);
    // This code is contributed by rag2127
</script>

Producción: 

John

Complejidad temporal: O(n)) , donde n es el número total de votos.
Espacio auxiliar: O(n), ya que se utiliza la estructura de datos unordered_map.

Otra solución eficiente es utilizar Trie . Consulte la palabra más frecuente en una serie de strings .

Este artículo es una contribución de Ishfaq Ramzan Nagoo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *