Dada una lista enlazada de tamaño N que consta de una string como valor de Node, la tarea es encontrar la string mayoritaria, que tenga una frecuencia mayor que [N/3] , en la lista enlazada.
Nota: Se garantiza que solo hay una string mayoritaria.
Ejemplos:
Entrada: cabeza -> geeks -> geeks -> abcd -> juego -> caballero -> geeks -> harry.
Salida: frikis.
Explicación:
La frecuencia de la string de geeks en la lista de enlaces es 3, que es mayor que [7/3], es decir, 2.Entrada: cabeza -> caliente -> caliente -> frío -> caliente -> caliente
Salida: caliente
Explicación:
La frecuencia de la string caliente en la lista de enlaces es 4, que es mayor que [5/3], es decir, 1.
Enfoque ingenuo:
almacene la frecuencia de cada string en un mapa . Recorre el mapa y busca la cuerda cuya frecuencia sea ≥ N / 3 .
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente:
la idea se basa en el algoritmo de votación de Moore .
Encuentre dos candidatos y verifique si alguno de estos dos candidatos es realmente un elemento mayoritario o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find an
// element with frequency
// of at least N / 3
// in a linked list
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
// for the linked list
struct node {
string i;
node* next = NULL;
};
// Utility function to
// create a node
struct node* newnode(string s)
{
struct node* temp = (struct node*)
malloc(sizeof(struct node));
temp->i = s;
temp->next = NULL;
return temp;
}
// Function to find and return
// the element with frequency
// of at least N/3
string Majority_in_linklist(node* head)
{
// Candidates for
// being the required
// majority element
string s = "", t = "";
// Store the frequencies
// of the respective candidates
int p = 0, q = 0;
node* ptr = NULL;
// Iterate all nodes
while (head != NULL) {
if (s.compare(head->i) == 0) {
// Increase frequency
// of candidate s
p = p + 1;
}
else {
if (t.compare(head->i) == 0) {
// Increase frequency
// of candidate t
q = q + 1;
}
else {
if (p == 0) {
// Set the new string as
// candidate for majority
s = head->i;
p = 1;
}
else {
if (q == 0) {
// Set the new string as
// second candidate
// for majority
t = head->i;
q = 1;
}
else {
// Decrease the frequency
p = p - 1;
q = q - 1;
}
}
}
}
head = head->next;
}
head = ptr;
p = 0;
q = 0;
// Check the frequency of two
// final selected candidate linklist
while (head != NULL) {
if (s.compare(head->i) == 0) {
// Increase the frequency
// of first candidate
p = 1;
}
else {
if (t.compare(head->i) == 0) {
// Increase the frequency
// of second candidate
q = 1;
}
}
head = head->next;
}
// Return the string with
// higher frequency
if (p > q) {
return s;
}
else {
return t;
}
}
// Driver Code
int main()
{
node* ptr = NULL;
node* head = newnode("geeks");
head->next = newnode("geeks");
head->next->next = newnode("abcd");
head->next->next->next
= newnode("game");
head->next->next->next->next
= newnode("game");
head->next->next->next->next->next
= newnode("knight");
head->next->next->next->next->next->next
= newnode("harry");
head->next->next->next->next->next->next
->next
= newnode("geeks");
cout << Majority_in_linklist(head) << endl;
return 0;
}
Java
// Java program to find an
// element with frequency
// of at least N / 3
// in a linked list
class GFG{
// Structure of a node
// for the linked list
static class node
{
String i;
node next = null;
};
// Utility function to
// create a node
static node newnode(String s)
{
node temp = new node();
temp.i = s;
temp.next = null;
return temp;
}
// Function to find and return
// the element with frequency
// of at least N/3
static String Majority_in_linklist(node head)
{
// Candidates for
// being the required
// majority element
String s = "";
String t = "";
// Store the frequencies
// of the respective candidates
int p = 0, q = 0;
node ptr = null;
// Iterate all nodes
while (head != null)
{
if (s.equals(head.i))
{
// Increase frequency
// of candidate s
p = p + 1;
}
else
{
if (t.equals(head.i))
{
// Increase frequency
// of candidate t
q = q + 1;
}
else
{
if (p == 0)
{
// Set the new string as
// candidate for majority
s = head.i;
p = 1;
}
else
{
if (q == 0)
{
// Set the new string as
// second candidate
// for majority
t = head.i;
q = 1;
}
else
{
// Decrease the frequency
p = p - 1;
q = q - 1;
}
}
}
}
head = head.next;
}
head = ptr;
p = 0;
q = 0;
// Check the frequency of two
// final selected candidate linklist
while (head != null)
{
if (s.equals(head.i))
{
// Increase the frequency
// of first candidate
p = 1;
}
else
{
if (t.equals(head.i))
{
// Increase the frequency
// of second candidate
q = 1;
}
}
head = head.next;
}
// Return the String with
// higher frequency
if (p > q)
{
return s;
}
else
{
return t;
}
}
// Driver Code
public static void main(String []arg)
{
node ptr = null;
node head = newnode("geeks");
head.next = newnode("geeks");
head.next.next = newnode("abcd");
head.next.next.next = newnode("game");
head.next.next.next.next = newnode("game");
head.next.next.next.next.next = newnode("knight");
head.next.next.next.next.next.next = newnode("harry");
head.next.next.next.next.next.next.next = newnode("geeks");
System.out.println(Majority_in_linklist(head));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to find an element
# with frequency of at least N / 3
# in a linked list
# Structure of a node
# for the linked list
class Node:
def __init__(self, s):
self.i = s
self.next = None
# Function to find and return
# the element with frequency
# of at least N/3
def Majority_in_linklist(head):
# Candidates for
# being the required
# majority element
s, t = "", ""
# Store the frequencies
# of the respective candidates
p, q = 0, 0
ptr = None
# Iterate all nodes
while head != None:
if s == head.i:
# Increase frequency
# of candidate s
p = p + 1
else:
if t == head.i:
# Increase frequency
# of candidate t
q = q + 1
else:
if p == 0:
# Set the new string as
# candidate for majority
s = head.i
p = 1
else:
if q == 0:
# Set the new string as
# second candidate
# for majority
t = head.i
q = 1
else:
# Decrease the frequency
p = p - 1
q = q - 1
head = head.next
head = ptr
p = 0
q = 0
# Check the frequency of two
# final selected candidate linklist
while head != None:
if s == head.i:
# Increase the frequency
# of first candidate
p = 1
else:
if t == head.i:
# Increase the frequency
# of second candidate
q = 1
head = head.next
# Return the string with
# higher frequency
if p > q:
return s
else:
return t
# Driver code
ptr = None
head = Node("geeks")
head.next = Node("geeks")
head.next.next = Node("abcd")
head.next.next.next = Node("game")
head.next.next.next.next = Node("game")
head.next.next.next.next.next = Node("knight")
head.next.next.next.next.next.next = Node("harry")
head.next.next.next.next.next.next.next = Node("geeks")
print(Majority_in_linklist(head))
# This code is contributed by stutipathak31jan
C#
// C# program to find an element with
// frequency of at least N / 3 in a
// linked list
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Structure of a node
// for the linked list
class node
{
public string i;
public node next = null;
};
// Utility function to
// create a node
static node newnode(string s)
{
node temp = new node();
temp.i = s;
temp.next = null;
return temp;
}
// Function to find and return
// the element with frequency
// of at least N/3
static string Majority_in_linklist(node head)
{
// Candidates for
// being the required
// majority element
string s = "";
string t = "";
// Store the frequencies
// of the respective candidates
int p = 0, q = 0;
node ptr = null;
// Iterate all nodes
while (head != null)
{
if (s.Equals(head.i))
{
// Increase frequency
// of candidate s
p = p + 1;
}
else
{
if (t.Equals(head.i))
{
// Increase frequency
// of candidate t
q = q + 1;
}
else
{
if (p == 0)
{
// Set the new string as
// candidate for majority
s = head.i;
p = 1;
}
else
{
if (q == 0)
{
// Set the new string as
// second candidate
// for majority
t = head.i;
q = 1;
}
else
{
// Decrease the frequency
p = p - 1;
q = q - 1;
}
}
}
}
head = head.next;
}
head = ptr;
p = 0;
q = 0;
// Check the frequency of two
// final selected candidate linklist
while (head != null)
{
if (s.Equals(head.i))
{
// Increase the frequency
// of first candidate
p = 1;
}
else
{
if (t.Equals(head.i))
{
// Increase the frequency
// of second candidate
q = 1;
}
}
head = head.next;
}
// Return the string with
// higher frequency
if (p > q)
{
return s;
}
else
{
return t;
}
}
// Driver Code
public static void Main(string []arg)
{
node head = newnode("geeks");
head.next = newnode("geeks");
head.next.next = newnode("abcd");
head.next.next.next = newnode("game");
head.next.next.next.next = newnode("game");
head.next.next.next.next.next = newnode("knight");
head.next.next.next.next.next.next = newnode("harry");
head.next.next.next.next.next.next.next = newnode("geeks");
Console.Write(Majority_in_linklist(head));
}
}
// This code is contributed by pratham76
Javascript
<script>
// JavaScript program to find an element with
// frequency of at least N / 3 in a
// linked list
// Structure of a node
// for the linked list
class node {
constructor() {
this.i = "";
this.next = null;
}
}
// Utility function to
// create a node
function newnode(s) {
var temp = new node();
temp.i = s;
temp.next = null;
return temp;
}
// Function to find and return
// the element with frequency
// of at least N/3
function Majority_in_linklist(head) {
// Candidates for
// being the required
// majority element
var s = "";
var t = "";
// Store the frequencies
// of the respective candidates
var p = 0,
q = 0;
var ptr = null;
// Iterate all nodes
while (head != null) {
if (s == head.i) {
// Increase frequency
// of candidate s
p = p + 1;
} else {
if (t == head.i) {
// Increase frequency
// of candidate t
q = q + 1;
} else {
if (p == 0) {
// Set the new string as
// candidate for majority
s = head.i;
p = 1;
} else {
if (q == 0) {
// Set the new string as
// second candidate
// for majority
t = head.i;
q = 1;
} else {
// Decrease the frequency
p = p - 1;
q = q - 1;
}
}
}
}
head = head.next;
}
head = ptr;
p = 0;
q = 0;
// Check the frequency of two
// final selected candidate linklist
while (head != null) {
if (s == head.i) {
// Increase the frequency
// of first candidate
p = 1;
} else {
if (t == head.i) {
// Increase the frequency
// of second candidate
q = 1;
}
}
head = head.next;
}
// Return the string with
// higher frequency
if (p > q) {
return s;
} else {
return t;
}
}
// Driver Code
var head = newnode("geeks");
head.next = newnode("geeks");
head.next.next = newnode("abcd");
head.next.next.next = newnode("game");
head.next.next.next.next = newnode("game");
head.next.next.next.next.next = newnode("knight");
head.next.next.next.next.next.next = newnode("harry");
head.next.next.next.next.next.next.next = newnode("geeks");
document.write(Majority_in_linklist(head));
// This code is contributed by rdtank.
</script>
Producción:
geeks
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA