Dado LinkedList, reemplace el valor de cada Node con su recuento de superadores. Esa es la cuenta de elementos que son mayores hacia su derecha.
Ejemplos:
Entrada: 10->12->5->40->21->70->1->49->37->NULL
Salida: 6->5->5->2->3->0-> 2->0->0->NULL
Explicación:
el elemento en el primer Node es 10 y el número de elementos a la derecha del Node que son mayores que 10 es 6 . Por lo tanto, reemplace el Node con 6 .
El elemento en el primer Node es 12 y el número de elementos a la derecha del Node que son mayores que 12 es 5 . Por lo tanto, reemplace el Node con 5 .
Del mismo modo, reemplace todos los elementos de la lista.
Entrada: 5->4->6->3->2->
1->1->0->0->0->NULO
Enfoque sencillo
- Tome dos punteros p y x . El puntero p se usa para recorrer la lista y x se usa para recorrer la mitad derecha de la lista para cada Node.
- Inicialice una cuenta variable para contar los Nodes mayores que los Nodes actuales.
- Recorra todos los Nodes de la lista con el puntero p.
- Inicializar el conteo a 0.
- Inicialice el puntero x para señalar el Node actual p .
- Cuente el número de Nodes que son mayores que el Node actual.
- Reemplace el Node actual con el conteo.
- Repita el paso 4 hasta recorrer la lista por completo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to replace the nodes
// with their surpasser count
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node {
int data;
struct Node* next;
};
// Utility function to create a new Node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// Function to display the linked list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Function to check Surpasser Count
void replaceNodes(Node* head)
{
// Pointer used to traverse through
// all the nodes in the list
Node* p = head;
// Pointer used to traverse through the right
// elements to count the greater elements
Node* x = NULL;
// Variable to count the number of
// elements greater than the
// current element on right
int count = 0;
int i;
// Traverse through all the elements
// in the list
while (p != NULL) {
count = 0;
i = 0;
// Initialize x to current node
x = p;
// Check or count the number of nodes
// that are greater than the current
// node on right
while (x != NULL) {
if (x->data > p->data)
count++;
x = x->next;
}
// Replace the node data with the
// count of elements greater than
// the current element
p->data = count;
p = p->next;
}
}
// Driver code
int main()
{
// Creating the linked list
Node* head = newNode(10);
head->next = newNode(12);
head->next->next = newNode(5);
head->next->next->next = newNode(40);
head->next->next->next->next = newNode(21);
head->next->next->next->next->next = newNode(70);
head->next->next->next->next->next->next = newNode(1);
head->next->next->next->next->next->next->next = newNode(49);
head->next->next->next->next->next->next->next->next = newNode(37);
replaceNodes(head);
printList(head);
return 0;
}
Java
// Java program to replace the nodes
// with their surpasser count
class GFG {
// A linked list node
static class Node {
int data;
Node next;
};
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to display the linked list
static void printList(Node node)
{
while (node != null) {
System.out.print(node.data+" ");
node = node.next;
}
}
// Function to check Surpasser Count
static void replaceNodes(Node head)
{
// Pointer used to traverse through
// all the nodes in the list
Node p = head;
// Pointer used to traverse through the right
// elements to count the greater elements
Node x = null;
// Variable to count the number of
// elements greater than the
// current element on right
int count = 0;
int i;
// Traverse through all the elements
// in the list
while (p != null) {
count = 0;
i = 0;
// Initialize x to current node
x = p;
// Check or count the number of nodes
// that are greater than the current
// node on right
while (x != null) {
if (x.data > p.data)
count++;
x = x.next;
}
// Replace the node data with the
// count of elements greater than
// the current element
p.data = count;
p = p.next;
}
}
// Driver code
public static void main(String[] args) {
// Creating the linked list
Node head = newNode(10);
head.next = newNode(12);
head.next.next = newNode(5);
head.next.next.next = newNode(40);
head.next.next.next.next = newNode(21);
head.next.next.next.next.next = newNode(70);
head.next.next.next.next.next.next = newNode(1);
head.next.next.next.next.next.next.next = newNode(49);
head.next.next.next.next.next.next.next.next = newNode(37);
replaceNodes(head);
printList(head);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to replace the nodes # with their surpasser count # A linked list node class Node: def __init__(self, data): self.data = data self.next = None # Function to display the linked list def printList(node): while node != None: print(node.data, end = " ") node = node.next # Function to check Surpasser Count def replaceNodes(head): # Pointer used to traverse through # all the nodes in the list p = head # Pointer used to traverse through # the right elements to count the # greater elements x = None # Variable to count the number of # elements greater than the # current element on right count = 0 # Traverse through all the elements # in the list while p != None: count = 0 # Initialize x to current node x = p # Check or count the number of nodes # that are greater than the current # node on right while x != None: if x.data > p.data: count += 1 x = x.next # Replace the node data with the # count of elements greater than # the current element p.data = count p = p.next # Driver code if __name__ == "__main__": # Creating the linked list head = Node(10) head.next = Node(12) head.next.next = Node(5) head.next.next.next = Node(40) head.next.next.next.next = Node(21) head.next.next.next.next.next = Node(70) head.next.next.next.next.next.next = Node(1) head.next.next.next.next.next.next.next = Node(49) head.next.next.next.next.next.next.next.next = Node(37) replaceNodes(head) printList(head) # This code is contributed by Rituraj Jain
C#
// C# program to replace the nodes
// with their surpasser count
using System;
class GFG
{
// A linked list node
public class Node
{
public int data;
public Node next;
};
// Utility function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to display the linked list
static void printList(Node node)
{
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
}
// Function to check Surpasser Count
static void replaceNodes(Node head)
{
// Pointer used to traverse through
// all the nodes in the list
Node p = head;
// Pointer used to traverse through the right
// elements to count the greater elements
Node x = null;
// Variable to count the number of
// elements greater than the
// current element on right
int count = 0;
int i;
// Traverse through all the elements
// in the list
while (p != null)
{
count = 0;
i = 0;
// Initialize x to current node
x = p;
// Check or count the number of nodes
// that are greater than the current
// node on right
while (x != null)
{
if (x.data > p.data)
count++;
x = x.next;
}
// Replace the node data with the
// count of elements greater than
// the current element
p.data = count;
p = p.next;
}
}
// Driver code
public static void Main()
{
// Creating the linked list
Node head = newNode(10);
head.next = newNode(12);
head.next.next = newNode(5);
head.next.next.next = newNode(40);
head.next.next.next.next = newNode(21);
head.next.next.next.next.next = newNode(70);
head.next.next.next.next.next.next = newNode(1);
head.next.next.next.next.next.next.next = newNode(49);
head.next.next.next.next.next.next.next.next = newNode(37);
replaceNodes(head);
printList(head);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to replace the nodes
// with their surpasser count
// A linked list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Utility function to create a new Node
function newNode( data)
{
var temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Function to display the linked list
function printList( node)
{
while (node != null) {
document.write(node.data+" ");
node = node.next;
}
}
// Function to check Surpasser Count
function replaceNodes( head)
{
// Pointer used to traverse through
// all the nodes in the list
var p = head;
// Pointer used to traverse through the right
// elements to count the greater elements
var x = null;
// Variable to count the number of
// elements greater than the
// current element on right
let count = 0;
let i;
// Traverse through all the elements
// in the list
while (p != null) {
count = 0;
i = 0;
// Initialize x to current node
x = p;
// Check or count the number of nodes
// that are greater than the current
// node on right
while (x != null) {
if (x.data > p.data)
count++;
x = x.next;
}
// Replace the node data with the
// count of elements greater than
// the current element
p.data = count;
p = p.next;
}
}
// Driver Code
// Creating the linked list
var head = newNode(10);
head.next = newNode(12);
head.next.next = newNode(5);
head.next.next.next = newNode(40);
head.next.next.next.next = newNode(21);
head.next.next.next.next.next = newNode(70);
head.next.next.next.next.next.next = newNode(1);
head.next.next.next.next.next.next.next = newNode(49);
head.next.next.next.next.next.next.next.next = newNode(37);
replaceNodes(head);
printList(head);
</script>
6 5 5 2 3 0 2 0 0
Complejidad de tiempo : O(N 2 ) donde N es el número de Nodes en la lista enlazada.
Espacio Auxiliar : O(1)
Otro enfoque con PBDS y mapa Hash
Podemos enumerar nuestros requisitos y enfoque para observar y encontrar una solución. Nuestro enfoque:
1. Recorra la lista enlazada desde atrás (para que no nos preocupemos por los elementos a la izquierda del actual)
2. Almacene el elemento actual en una estructura de datos ordenados (en cualquier momento, los elementos se ordenan en nuestra estructura de datos)
3. Encuentre el número total de elementos mayor que el elemento actual en nuestra estructura de datos ordenados y reemplace el elemento actual con él
Para recorrer la lista enlazada hacia atrás, usaremos la recursividad.
Podemos usar PBDS. Con PBDS podemos encontrar elementos estrictamente más pequeños que una clave en particular. Con estrictamente más pequeño, podemos agregar el elemento actual y restarlo de todos los elementos. Así que básicamente:
Elementos mayores que el actual = Elementos Totales en PBDS – (Consulta en PBDS para encontrar elementos estrictamente menores) – (Elemento actual + elemento igual al actual)
PBDS no permite elementos duplicados. Pero para la parte de conteo, necesitamos elementos duplicados. Así que insertaremos un par en PBDS (primero = elemento, segundo = índice) para que cada entrada sea única. Después de eso, para encontrar elementos totales iguales al elemento actual, usaremos un mapa hash. En el mapa hash almacenaremos las ocurrencias totales de un elemento (un mapa básico de entero a entero).
NOTA : También podemos construir nuestra propia estructura de datos que cumpla con los requisitos actuales como dijimos. Insertar duplicados en orden ordenado y consultar elementos justo mayores que la clave. Pero usaremos C++ STL DS para hacerlo en esta publicación.
C++
#include <iostream>
#include <unordered_map>
// library for PBS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// PBDS of pair<int, int>
#define oset tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
// Linked list storage
class Node {
public:
int value;
Node* next;
Node(int value) {
this->value = value;
next = NULL;
}
};
/*
head => head is the head of the linked list
os => unordered_set or PBDS
mp => Hash map to store count of each element
count => count of element from backwards
*/
void solve(Node* head, oset& os, unordered_map<int, int>& mp, int& count) {
if(head == NULL) return;
solve(head->next, os, mp, count);
// we first call our recursion and then compute to traverse the linked list backwards on recursion return
// increment count backwards
count++;
// inserting elements into PBDS with indexes starting from backwards
os.insert({head->value, count});
// mapping elements to count
mp[head->value]++;
// formula: total elements in PBDS - total number of elements equal to current - elements smaller than current
int numberOfElements = count - mp[head->value] - os.order_of_key({head->value, -1});
// replace the linked list current element to the number of elements greater than the current
head->value = numberOfElements;
}
void printList(Node* head) {
while(head) {
cout << head->value << (head->next ? "->" : "");
head = head->next;
}
cout << "\n";
}
int main() {
Node* head = new Node(43);
head->next = new Node(65);
head->next->next = new Node(12);
head->next->next->next = new Node(46);
head->next->next->next->next = new Node(68);
head->next->next->next->next->next = new Node(85);
head->next->next->next->next->next->next = new Node(59);
head->next->next->next->next->next->next->next = new Node(85);
head->next->next->next->next->next->next->next->next = new Node(37);
oset os;
unordered_map<int, int> mp;
int count = 0;
printList(head);
solve(head, os, mp, count);
printList(head);
return 0;
}
43->65->12->46->68->85->59->85->37 6->3->6->4->2->0->1->0->0
La complejidad del espacio de nuestro algoritmo es O (n) ya que almacenamos los elementos en PBDS y hash para contar. La complejidad del tiempo es O(n*log(n)) ya que insert y order_of_key de PBDS usa log(n) y el mapa hash toma O(1).