Dada una lista enlazada, encuentre el elemento mayoritario. Un elemento se denomina elemento mayoritario si aparece más o igual a n/2 veces, donde n es el número total de Nodes en la lista enlazada.
Ejemplos:
Input : 1->2->3->4->5->1->1->1->NULL Output : 1 Explanation 1 occurs 4 times Input :10->23->11->9->54->NULL Output :NO majority element
Método 1 (simple)
Ejecute dos bucles a partir de la cabeza y cuente la frecuencia de cada elemento de forma iterativa. Imprime el elemento cuya frecuencia es mayor o igual a n/2. En este enfoque, la complejidad del tiempo será O(n*n) donde n es el número de Nodes en la lista enlazada.
C++
// C++ program to find majority element in
// a linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to get the nth node from the
last of a linked list*/
int majority(struct Node* head)
{
struct Node* p = head;
int total_count = 0, max_count = 0, res = -1;
while (p != NULL) {
// Count all occurrences of p->data
int count = 1;
struct Node* q = p->next;
while (q != NULL) {
if (p->data == q->data)
count++;
q = q->next;
}
// Update max_count and res if count
// is more than max_count
if (count > max_count)
{
max_count = count;
res = p->data;
}
p = p->next;
total_count++;
}
if (max_count >= total_count/2)
return res;
// if we reach here it means no
// majority element is present.
// and we assume that all the
// element are positive
return -1;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
// create linked
push(&head, 1);
push(&head, 1);
push(&head, 1);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
int res = majority(head);
if (res != (-1))
cout << "Majority element is " << res;
else
cout << "No majority element";
return 0;
}
Java
// Java program to find majority element in
// a linked list
import java.util.*;
class GFG
{
static Node head;
/* Link list node */
static class Node
{
int data;
Node next;
};
/* Function to get the nth node from
the last of a linked list*/
static int majority(Node head)
{
Node p = head;
int total_count = 0,
max_count = 0, res = -1;
while (p != null)
{
// Count all occurrences of p->data
int count = 1;
Node q = p.next;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
// Update max_count and res if count
// is more than max_count
if (count > max_count)
{
max_count = count;
res = p.data;
}
p = p.next;
total_count++;
}
if (max_count >= total_count / 2)
return res;
// if we reach here it means no
// majority element is present.
// and we assume that all the
// element are positive
return -1;
}
static void push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// Driver Code
public static void main(String[] args)
{
/* Start with the empty list */
head = null;
// create linked
push(head, 1);
push(head, 1);
push(head, 1);
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 2);
push(head, 1);
int res = majority(head);
if (res != (-1))
System.out.println("Majority element is " + res);
else
System.out.println("No majority element");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find majority element in
# a linked list
head = None
# Link list node
class Node :
def __init__(self):
self.data = 0
self.next = None
# Function to get the nth node from
# the last of a linked list
def majority(head):
p = head
total_count = 0
max_count = 0
res = -1
while (p != None):
# Count all occurrences of p->data
count = 1
q = p.next
while (q != None):
if (p.data == q.data):
count = count + 1
q = q.next
# Update max_count and res if count
# is more than max_count
if (count > max_count):
max_count = count
res = p.data
p = p.next
total_count = total_count + 1
if (max_count >= total_count / 2):
return res
# if we reach here it means no
# majority element is present.
# and we assume that all the
# element are positive
return -1
def push( head_ref, new_data):
global head
new_node = Node()
new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
head = head_ref
# Driver Code
# Start with the empty list
head = None
# create linked
push(head, 1)
push(head, 1)
push(head, 1)
push(head, 5)
push(head, 4)
push(head, 3)
push(head, 2)
push(head, 1)
res = majority(head)
if (res != (-1)):
print("Majority element is " , res)
else:
print("No majority element")
# This code is contributed by Arnab Kundu
C#
// C# program to find majority element in
// a linked list
using System;
class GFG
{
static Node head;
/* Link list node */
public class Node
{
public int data;
public Node next;
};
/* Function to get the nth node from
the last of a linked list*/
static int majority(Node head)
{
Node p = head;
int total_count = 0,
max_count = 0, res = -1;
while (p != null)
{
// Count all occurrences of p->data
int count = 1;
Node q = p.next;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
// Update max_count and res if count
// is more than max_count
if (count > max_count)
{
max_count = count;
res = p.data;
}
p = p.next;
total_count++;
}
if (max_count >= total_count / 2)
return res;
// if we reach here it means no
// majority element is present.
// and we assume that all the
// element are positive
return -1;
}
static void push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// Driver Code
public static void Main(String[] args)
{
/* Start with the empty list */
head = null;
// create linked
push(head, 1);
push(head, 1);
push(head, 1);
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 2);
push(head, 1);
int res = majority(head);
if (res != (-1))
Console.WriteLine("Majority element is " + res);
else
Console.WriteLine("No majority element");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find majority element in
// a linked list
var head = null;
/* Link list node */
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
/* Function to get the nth node from
the last of a linked list*/
function majority(head)
{
var p = head;
var total_count = 0,
max_count = 0, res = -1;
while (p != null)
{
// Count all occurrences of p->data
var count = 1;
var q = p.next;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
// Update max_count and res if count
// is more than max_count
if (count > max_count)
{
max_count = count;
res = p.data;
}
p = p.next;
total_count++;
}
if (max_count >= total_count / 2)
return res;
// if we reach here it means no
// majority element is present.
// and we assume that all the
// element are positive
return -1;
}
function push(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// Driver Code
/* Start with the empty list */
head = null;
// create linked
push(head, 1);
push(head, 1);
push(head, 1);
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 2);
push(head, 1);
var res = majority(head);
if (res != (-1))
document.write("Majority element is " + res);
else
document.write("No majority element");
</script>
Producción
Majority element is 1
Tiempo Complejidad O(n*n)
Método 2 Usar técnica hash. Contamos la frecuencia de cada elemento y luego imprimimos el elemento cuya frecuencia es ≥ n/2;
C++
// CPP program to find majority element
// in the linked list using hashing
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to get the nth node from the last
of a linked list*/
int majority(struct Node* head)
{
struct Node* p = head;
// Storing elements and their frequencies
// in a hash table.
unordered_map<int, int> hash;
int total_count = 0;
while (p != NULL) {
// increase every element
// frequency by 1
hash[p->data]++;
p = p->next;
total_count++;
}
// Check if frequency of any element
// is more than or equal to total_count/2
for (auto x : hash)
if (x.second >= total_count/2)
return x.first;
// If we reach here means no majority element
// is present. We assume that all the element
// are positive
return -1;
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Driver program to test above function
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 1);
push(&head, 1);
push(&head, 1);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
int res = majority(head);
if (res != (-1))
cout << "majority element is " << res;
else
cout << "NO majority element";
return 0;
}
Java
// JAVA program to find majority element
// in the linked list using hashing
import java.util.*;
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
};
/* Function to get the nth node from the last
of a linked list*/
static int majority(Node head)
{
Node p = head;
// Storing elements and their frequencies
// in a hash table.
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
int total_count = 0;
while (p != null)
{
// increase every element
// frequency by 1
if(hash.containsKey(p.data))
hash.put(p.data, hash.get(p.data) + 1);
else
hash.put(p.data, 1);
p = p.next;
total_count++;
}
// Check if frequency of any element
// is more than or equal to total_count/2
for (Map.Entry<Integer,Integer> x : hash.entrySet())
if (x.getValue() >= total_count/2)
return x.getKey();
// If we reach here means no majority element
// is present. We assume that all the element
// are positive
return -1;
}
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
// Driver code
public static void main(String[] args)
{
/* Start with the empty list */
Node head = null;
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
int res = majority(head);
if (res != (-1))
System.out.print("majority element is " + res);
else
System.out.print("NO majority element");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find majority element
# in the linked list using hashing
''' Link list node '''
class Node:
def __init__(self, data):
self.data = data
self.next = None
''' Function to get the nth node from the last
of a linked list'''
def majority(head):
p = head;
# Storing elements and their frequencies
# in a hash table.
hash = dict()
total_count = 0;
while (p != None):
# increase every element
# frequency by 1
if p.data not in hash:
hash[p.data] = 0
hash[p.data] += 1
p = p.next;
total_count += 1
# Check if frequency of any element
# is more than or equal to total_count/2
for x in hash.keys():
if (hash[x] >= total_count//2):
return x;
# If we reach here means no majority element
# is present. We assume that all the element
# are positive
return -1;
def push(head_ref, new_data):
new_node = Node(new_data)
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref
# Driver code
if __name__=='__main__':
''' Start with the empty list '''
head = None
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
res = majority(head);
if (res != (-1)):
print("majority element is " + str(res))
else:
print("NO majority element")
# This code is contributed by rutvik_56
C#
// C# program to find majority element
// in the linked list using hashing
using System;
using System.Collections.Generic;
class GFG
{
/* Link list node */
public class Node
{
public int data;
public Node next;
};
/* Function to get the nth node
from the last of a linked list*/
static int majority(Node head)
{
Node p = head;
// Storing elements and their frequencies
// in a hash table.
Dictionary<int,
int> hash = new Dictionary<int,
int>();
int total_count = 0;
while (p != null)
{
// increase every element
// frequency by 1
if(hash.ContainsKey(p.data))
hash[p.data] = hash[p.data] + 1;
else
hash.Add(p.data, 1);
p = p.next;
total_count++;
}
// Check if frequency of any element
// is more than or equal to total_count/2
foreach(KeyValuePair<int, int> x in hash)
if (x.Value >= total_count/2)
return x.Key;
// If we reach here means no majority element
// is present. We assume that all the element
// are positive
return -1;
}
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
// Driver code
public static void Main(String[] args)
{
/* Start with the empty list */
Node head = null;
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
int res = majority(head);
if (res != (-1))
Console.Write("majority element is " + res);
else
Console.Write("NO majority element");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find majority element
// in the linked list using hashing
/* Link list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/* Function to get the nth node
from the last of a linked list*/
function majority(head)
{
var p = head;
// Storing elements and their frequencies
// in a hash table.
var hash = {};
var total_count = 0;
while (p != null)
{
// increase every element
// frequency by 1
if (hash.hasOwnProperty(p.data)) hash[p.data] = hash[p.data] + 1;
else hash[p.data] = 1;
p = p.next;
total_count++;
}
// Check if frequency of any element
// is more than or equal to total_count/2
for (const [key, value] of Object.entries(hash)) {
if (value >= parseInt(total_count / 2)) return key;
// If we reach here means no majority element
// is present. We assume that all the element
// are positive
return -1;
}
}
function push(head_ref, new_data) {
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
// Driver code
/* Start with the empty list */
var head = null;
head = push(head, 1);
head = push(head, 1);
head = push(head, 1);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
var res = majority(head);
if (res != -1) document.write("majority element is " + res);
else document.write("NO majority element");
// This code is contributed by rdtank.
</script>
Tiempo Complejidad O(n)
Salida:
majority element is 1
Publicación traducida automáticamente
Artículo escrito por Vishal_Khoda y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA